文章目录
KMP
前缀表(教材的next数组)
最长公共前后缀
KMP模板
#include<bits/stdc++.h> using namespace std; // 建立前缀表 void prefix_table(char p[], int prefix[], int n){ prefix[0] = 0; int len = 0; int i = 1; // 从第一个字母开始比较 while( i<n ){ if(p[i] == p[len] ){ len++; prefix[i] = len; i++; } else{ if(len>0){ len = prefix[len-1]; } else{ prefix[i] = 0; i++; } } } } // 脱落最后一位 void move_prefix( int prefix[], int n){ for(int i=n-1; i>0; i--){ prefix[i] = prefix[i-1]; } prefix[0] = -1; } void KMP_search(char text[], char pattern[]) { int n = strlen(pattern); int m = strlen(text); int * prefix = new int[n]; prefix_table(pattern, prefix, n); move_prefix(prefix,n); // text[i] len(text) = m // pattern[j] len(pattern) = n int i=0, j=0; while( i < m ){ if( ( j == n-1 ) && ( text[i]==pattern[j] )){ printf("Fount pattern at %d\n", i-j ); j = prefix[j]; } if(text[i] == pattern[j]){ i++; j++; } else{ j = prefix[j]; if(j == -1) { i++; j++; } } } delete prefix; } int main() { char pa[] = "abcdab"; char te[] = "ababcdabasd"; KMP_search(te,pa); return 0; }
2、串替换
题目描述
给出主串、模式串、替换串，用KMP算法找出模式串在主串的位置，然后用替换串的字符替换掉模式串
本题只考虑一处替换的情况，如果你想做的完美一些，能够实现多处替换那可能需要考虑模式串和替换串长度不一致的情况
输入
第一个输入t，表示有t个实例
第二行输入第1个实例的主串，第三行输入第1个实例的模式串，第四行输入第1个实例的替换串
以此类推
输出
第一行输出第1个实例的主串
第二行输出第1个实例的主串替换后结果，如果没有发生替换就输出主串原来的内容。
以此类推
样例输入
4 aabbccdd bb ff aaabbbccc ddd eee abcdef abc ccccc abcdef abc c
样例输出
aabbccdd aaffccdd aaabbbccc aaabbbccc abcdef cccccdef abcdef cdef
#include <iostream> #include <string> using namespace std; class myString { private: int size; void GetNext(string p,int next[]); int KMPFind(string p,int pos,int next[]); public: string mainstr; myString(); ~myString(); void SetVal(string sp); int KMPFindSubstr(string p,int pos); void tihuan(string p,int pos,int molen); }; myString::myString() { size = 0; mainstr=""; } myString::~myString() { size = 0; mainstr=""; } void myString::SetVal(string sp) { mainstr = ""; mainstr.assign(sp); size = mainstr.length(); } void myString::GetNext(string p,int next[]) { next[0] = -1; int i = 0,now =-1; while(i<int(p.length())) { if(now==-1||p[i]==p[now]) { i++; now++; next[i]=now; }else { now = next[now]; } } } int myString::KMPFind(string p,int pos,int next[]) { int i=pos,j=0; while(i<size&&j<int(p.length())) { if(j==-1||mainstr[i]==p[j]) { i++; j++; }else { j=next[j]; } } if(j==int(p.length())) return i-j+1; else return 0; } int myString::KMPFindSubstr(string p,int pos) { int i; int L=p.length(); int *next = new int [L]; GetNext(p,next); // for(int i=0;i<L;i++) // { // cout<<next[i]<<" "; // } // cout<<endl; int v=-1; v = KMPFind(p,0,next); delete []next; return v; } void myString::tihuan(string p,int pos,int molen) { int len = p.length(); string sub1 = mainstr.substr(0,pos); string sub2 = mainstr.substr(pos+molen); mainstr = sub1+p+sub2; } int main() { int t; cin>>t; while(t--) { string mainstr,mostr,tihuanstr; cin>>mainstr>>mostr>>tihuanstr; myString ms; ms.SetVal(mainstr); int molen = mostr.length(); int pos = ms.KMPFindSubstr(mostr,0)-1; cout<<ms.mainstr<<endl; if(pos!=-1) { ms.tihuan(tihuanstr,pos,molen); } cout<<ms.mainstr<<endl; } }
