void getnext(const char P[], int next[])
{
int q, k;
int m = strlen(P); // 模板字符串的长度
next[0] = 0;
for(q = 1, k = 0; q < m; ++q) { // 从第二个字符开始，依次计算每个字符对应的next值
while(k > 0 && P[q] != P[k]) {
k = next[k-1];
}
if(P[q] == P[k]) {
k++;
}
next[q] = k;
}
}
int kmp(const char T[], const char P[], int next[])
{
int n, m;
int i, q;
n = strlen(T);
m = strlen(P);
getnext(P, next); // 计算next数组
for(i = 0, q = 0; i < n; ++i) {
while(q > 0 && P[q] != T[i]) {
q = next[q-1];
}
if(P[q] == T[i]) q++;
if(q == m) {
// 输出找到的位置
cout << (i-m+1) << endl;
}
}
}
kmp算法
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 最近研究了一下kmp算法(Knuth-Morris-Pratt)，百度了好多帖子，看的稀里糊涂。为了自己可以简单理...
- 前言 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision pr...
