从键盘输入字符文件名以及子串,用改进KMP算法在字符文件中实现子串查找。要求程序输出子串的改进nextval数组元素值以及子串在文件中成功匹配的次数(查找失败输出成功匹配次数为0),c++语言
3条回答 默认 最新
- coolsunxu 2017-04-28 05:11关注
#include<iostream> #include<string.h> using namespace std; int *COMPUTE_PREFIX_FUNCTION(string P) { int m=P.size(); int *A=new int[m+1]; A[1]=0; int k=0; for(int q=2;q<=m;q++) { while(k>0 && P[k]!=P[q-1]) { k=A[k]; } if(P[k]==P[q-1]) { k++; A[q]=k; } } return A; } void KMP_MATCHER(string T,string P) { int n=T.size(); int m=P.size(); int *A=COMPUTE_PREFIX_FUNCTION(P); int q=0; for(int i=1;i<=n;i++) { while(q>0 && P[q]!=T[i-1]) { q=A[q]; } if(P[q]==T[i-1]) { q++; } if(q==m) { cout<<"Pattern occurs with shift "<<i-m+1<<endl; q=A[q]; } } } int main() { string P,T; cout<<"请输入父字符串:"; cin>>T; cout<<"请输入父字符串:"; cin>>P; KMP_MATCHER(T,P); return 0; } /* abctergytrabcgregabcdsfabcf abc */
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报