算法导论-KMP模版

本文主要是介绍算法导论-KMP模版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;const int maxn = 10001;
int next[maxn];void Compute(char *p)   //匹配串和自己的next值
{int m = strlen(p+1);memset(next,0,sizeof(next));next[1] = 0;int k = 0;for(int q = 2;q<=m;q++){while(k > 0 && p[k+1] != p[q]){k = next[k];}if(p[k+1] == p[q]){k++;}next[q] = k;}
}void KMP_MATCHER(char *t,char *p)
{int n = strlen(t+1);int m = strlen(p+1);Compute(p);int q = 0;for(int i=1;i<=n;i++){while(q > 0 && p[q + 1] != t[i])  //如果匹配不想等那么匹配串就回溯，回溯到记录的next数组那个位置{q = next[q];}if(p[q+1] == t[i])  //如果匹配成功就匹配下一个位置{q++;}if(q == m)  //已经成功匹配{cout<<"matching complete!shift:"<<i-m<<endl;  //如果匹配成功输出并返回总共移动了几个位置q = next[q];}}
}int main()
{char str1[maxn];char str2[maxn];int i;scanf("%s%s",str1+1,str2+1);KMP_MATCHER(str1,str2);return 0;
}

这篇关于算法导论-KMP模版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---