|
楼主 |
发表于 2014-10-2 20:35:49
|
显示全部楼层
修改好的 KMP 算法:- #include <stdio.h>
- #include <stdlib.h>
- typedef char* String;
- // KMP 算法start
- /*
- 获取 KMP 的 next 数组
- */
- void getNext(String T, int *next)
- {
- int j = -1; // 前
- int i = 0; // 后
- next[0] = -1; // next数组第一个元素为-1
- int lenT = strlen(T); // 字符串长度
- while( i < lenT)
- {
- // 刚开始or匹配相等加1向前走(BF原則)
- if(-1==j || T[i] == T[j])
- {
- j++;
- i++;
- if(T[i] != T[j])
- {
- next[i] = j; // 填下一个
- }
- else
- {
- next[i] = next[j];
- }
- }
- else
- {
- j = next[j];
- }
- }
- }
- // 返回子串T在主串S第pos个字符之后的位置
- // 若存在,返回-1
- int indexKMP(String S, String T, int pos)
- {
- int i = pos;
- int j = 0;
- int next[255];
- getNext(T, next); // 获取next数组
- int lenS = strlen(S);
- int lenT = strlen(T);
- while(i<lenS && j<lenT)
- {
- if(-1 == j || S[i] == T[j]) //j=-1,没有这个元素,指向下一个元素,类似BF算法
- {
- i++;
- j++;
- }
- else // 匹配失败
- {
- j = next[j];
- }
- }
- if(j > lenT - 1)
- {
- return i - lenT;
- }
- else
- {
- return -1;
- }
- }
- // KMP 算法end
- int main()
- {
- i = indexKMP("ababaaabacca", "aaaa", 0);
- printf("KMP, index: %d ", i);
- printf("\n");
- return 0;
- }
复制代码
|
|