KMP算法学习笔记

参考http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

部分代码原作:http://www.cnblogs.com/Topless/archive/2011/10/16/2214450.html

java代码:

public class KPM {

// java实现kpm算法
// 算法原理:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
// http://v.youku.com/v_show/id_XOTMyMjcxNzIw.html?from=s1.8-1-1.2七月算法视频

// KMP中的核心算法,获得记录跳转状态的next数组
public static int[] next1(String sub) {
int[] a = new int[sub.length()];
char[] c = sub.toCharArray();
int length = sub.length();
int i, j;
a[0] = -1;
i = 0;
for (j = 1; j < length; j++) {
i = a[j - 1];
while (i >= 0 && c[j] != c[i + 1]) {
i = a[i];
}
if (c[j] == c[i + 1]) {
a[j] = i + 1;
} else {
a[j] = -1;
}
}
return a;
}

//与上面算法思路一致,换一种写法
public static int[] next2(String sub) {
int[] next = new int[sub.length()];
char[] c = sub.toCharArray();
int length = sub.length();
next[0] = -1;
int k=-1,j=0;
while(j<length-1){
if(k==-1 || c[j]==c[k]){
++k;
++j;
if(c[j]==c[k]){
next[j]=next[k];
}else{
next[j]=k;
}
}else{
k=next[k];
}
}
return next;
}

public static void pattern(String str, String sub, int[] next) {
char[] ch1 = str.toCharArray();
char[] ch2 = sub.toCharArray();
int i = 0, j = 0; // i控制ch1,j控制ch2;
for (; i < ch1.length;) {
if (ch1[i] == ch2[j]) {// 匹配就自动递增，往后匹配。
if (j == ch2.length - 1) {
System.out.println(i - ch2.length + 1);
break;
}
j++;
i++;
} else if (j == 0) {
i++;
} else {
j = next[j - 1] + 1;
}
}
}

public static void main(String[] args) {
String sub = "aabaccfaddddaabc";
String str = "gdsaadfdgffccsdaabaccfdaddaabaccfaddddaabcga";
int[] next = next(sub);
pattern(str, sub, next);
}
}

视频笔记:

BF算法,最一般的暴力破解算法:

int BruteForceSearch(const char* s,const char * p){
    int i=0;    //当前匹配到的原始串首位
    int j=0;    //模式串的匹配位置
    int size=(int)strlen(s);
    int psize=(int)strlen(p);
    while((i<size) && (j<psize)){
        if(s[i-j]==p[j]){
            j++;
        }else{
            i++;
            j=0;    //暴力法最大问题在于j=0
        }
    }
    if(j>=psize){
        return i;
    }
    return -1;
}

kpm就是要改变j=0这一步
next函数:

void CalcNext(char* p,int next[]){
    int nLen=strlen(p);
    next[0]=-1;
    int k=-1;
    int j=0;
    while(j<nLen-1){
        //此刻,k即next[j-1],且p[k]表示前缀,p[j]表示后缀
        //注:k==-1表示未找到前缀与k后缀相等,首次分析可先忽略
        if(k==-1 || p[j]==p[k]){
            ++k;
            ++j;
            if(p[j]==p[k]){
                next[j]=next[k];
            }else{
                next[j]=k;
            }
        }else{  //p[j]与p[k]匹配失败,则继续递归前缀索引p[next[k]]
            k=next[k];
        }
    }
}

int KMP(int n){    int ans=-1;    int i=0;    int j=0;    int pattern_len=strlen(g_pattern);    while(i<n){        if(j==-1 || g_s[i]==g_pattern[j]){            ++i;            ++j;        }else{            j=g_next[j];        }        if(j==pattern_len){            //找到结果            ans=i-pattern_len;            break;        }    }    return ans;}