資訊專欄INFORMATION COLUMN
摘要：原理代碼部分匹配表匹配位置下一個(gè)比較位置記錄所有匹配的子串記錄子串匹配位置相等子串匹配完畢，記錄位置，并且找下一個(gè)匹配的子串子串匹配位置加如果子串位置不匹配的話從匹配表里面找到子串新的匹配位置接著比較輸出結(jié)果
原理：http://www.ruanyifeng.com/blo...
代碼
import java.util.Arrays;
public class KMP {
private static int[] prefixTable;
/**
* 部分匹配表
* @param t
* @return
*/
public int[] getPrefixTable(char[] t){
int n = t.length;
int len;//匹配位置
prefixTable = new int[n];
prefixTable[0] = 0;
for(int i = 1;i < n;i++){
len = prefixTable[i - 1];
while(true){
if(t[len] == t[i]){
len++;
prefixTable[i] = len;
break;
}else{
if(len > 0)//下一個(gè)比較位置
len = prefixTable[len - 1];
else{
prefixTable[i] = 0;//
break;
}
}
}
}
return prefixTable;
}
public int[] match(char[] s,char[] t){
int[] result = new int[s.length];//記錄所有匹配的子串
int count = 0;
int j = 0;//記錄子串匹配位置
for(int i = 0;i < s.length;i++){
if(s[i] == t[j]){//相等
if(j == t.length - 1){//子串匹配完畢，記錄位置，并且j=0找下一個(gè)匹配的子串
result[count++] = i - t.length + 1;
j = 0;
}else{//子串匹配位置加1
j++;
}
}else{
if(j > 0){//如果子串位置＞0
j = prefixTable[j - 1];//不匹配的話從匹配表里面找到子串新的匹配位置
i--;//接著比較
}
}
}
return result;
}
public static void main(String[] args) {
KMP kmp= new KMP();
char[] s = "ABCDAB ABCDABCDABDEABCDABD".toCharArray();
char[] t = "ABCDABD".toCharArray();
kmp.getPrefixTable(t);
int index[] = kmp.match(s, t);
System.out.println(Arrays.toString(index));
}
}
輸出結(jié)果
[11, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/74890.html
摘要：字符串的普通模式匹配普通模式匹配的原理不進(jìn)行說(shuō)明了，簡(jiǎn)單來(lái)說(shuō)就是兩個(gè)字符串的每個(gè)字符依次進(jìn)行匹配。 這篇文章主要是介紹KMP模式匹配算法，在正式介紹KMP之前我們先看一下普通模式匹配，由普通模式匹配在進(jìn)一步的推導(dǎo)KMP模式會(huì)更容易理解。 字符串的普通模式匹配 普通模式匹配的原理不進(jìn)行說(shuō)明了，簡(jiǎn)單來(lái)說(shuō)就是兩個(gè)字符串的每個(gè)字符依次進(jìn)行匹配。 public int match(String ...
摘要：第一種方法常規(guī)方法。如果不存在公共前綴，返回空字符串。注意假設(shè)字符串的長(zhǎng)度不會(huì)超過(guò)。說(shuō)明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個(gè)可能的最長(zhǎng)回文子序列為。數(shù)值為或者字符串不是一個(gè)合法的數(shù)值則返回。 說(shuō)明 本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點(diǎn)：https://www.weiweiblog.c...
摘要：算法代碼復(fù)雜度最壞情況的時(shí)間復(fù)雜度。算法簡(jiǎn)單記憶分為兩步模式串掃描，生成數(shù)組，。算法對(duì)算法的回溯問(wèn)題進(jìn)行了改進(jìn)，在整個(gè)匹配過(guò)程中對(duì)主串僅需從頭至尾掃描一遍。在定義函數(shù)時(shí)在參數(shù)前加上改為引傳遞。一般情況為值傳遞，對(duì)象除外。 BF算法 代碼 復(fù)雜度 最壞情況的時(shí)間復(fù)雜度O(m*n)。m為模式串長(zhǎng)度。n為目標(biāo)串長(zhǎng)度。 KMP算法 代碼 時(shí)間復(fù)雜度 時(shí)間復(fù)雜度為O(m+n)。m為模式串長(zhǎng)度...
摘要：寫在最前本次分享一下通過(guò)實(shí)現(xiàn)算法的動(dòng)畫效果來(lái)試圖展示的基本思路。算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。本次主要通過(guò)動(dòng)畫演示的方式展現(xiàn)樸素算法與算法對(duì)比過(guò)程的異同從而試圖理解的基本思路。 寫在最前 本次分享一下通過(guò)實(shí)現(xiàn)kmp算法的動(dòng)畫效果來(lái)試圖展示kmp的基本思路。 歡迎關(guān)注我的博客，不定期更新中—— 前置概念 字符串匹配 字符串匹配是計(jì)算...
閱讀 5052·2021-11-25 09:43
閱讀 1695·2021-10-27 14:18
閱讀 1063·2021-09-22 16:03
閱讀 1356·2019-08-30 13:19
閱讀 1579·2019-08-30 11:15
閱讀 1649·2019-08-26 14:04
閱讀 3128·2019-08-23 18:40
閱讀 1168·2019-08-23 18:17
