深入理解KMP算法
時(shí)間：20180313
KMP算法的核心是 求公共最大前后綴良蒸。
public class Prefix {
//求前綴后綴的最長(zhǎng)子串
public static int [] getPrefix(char patern[]){
int [] prefix = new int [patern.length];
//第一個(gè)前后綴最長(zhǎng)子綴為0
prefix[0] = 0;
int i = 1;
while(i < patern.length){
//System.out.println("i: "+ i +" prefix[i] : "+ prefix[i]);
//正常情況下：當(dāng)前值(第i個(gè)值)等于前面一串的字符串已知prefix[i-1]的情況下去判斷
//當(dāng)前值patern[i]與patern[prefix[i-1]]的大小载萌，若相等則在patern[prefix[i-1]]基礎(chǔ)上加1
//若不相等繼續(xù)進(jìn)行判斷洪添，判斷邏輯見(jiàn)畫(huà)圖分析
if(patern[i] == patern[prefix[i-1]]){
prefix[i] = prefix[i-1] + 1;
i++;
}else{
//處理當(dāng)前值patern[i]與patern[prefix[i-1]]不相等的情況
if(prefix[i-1] > 0){
//取得右偏一位后值的最大公共前后綴
prefix[i] = prefix[prefix[i-1]-1];
i++;
}else{
prefix[i] = 0;
//防止死循環(huán)
i++;
}
}
}
return prefix;
}
//將prefix數(shù)組中的值逐步向后移動(dòng)一位
public static int[] movePrefix(int[] prefix){
for(int i= prefix.length-1; i > 0; i--){
prefix[i] = prefix[i-1];
}
prefix[0] = -1;
return prefix;
}
public static void main(String[] args) {
String s = "ABABCABAA";
System.out.println(s);
char [] patern = s.toCharArray();
int [] res = getPrefix(patern);
res = movePrefix(res);
for(int i = 0; i < res.length; i++){
System.out.println(res[i]);
}
}
}
畫(huà)圖分析
對(duì)前后綴最大長(zhǎng)度的分析
繼續(xù)分析如何利用前后綴最大長(zhǎng)度數(shù)組進(jìn)行字符串匹配的過(guò)程
參考
https://search.bilibili.com/all?keyword=kmp&from_source=banner_search
https://www.bilibili.com/video/av16828557/?from=search&seid=4786796467366856321
