对于扩展kmp,现在还没有进行实用,所以先将模板打好基础,理解清楚每一步,这样日后应用就轻松点了。
对于这个模板,我觉得主要以理解扩展kmp为主,赛场实战的时候可以适当简化,这个模板对着 刘琼雅的 那个扩展kmp的ppt,可以很好的理解和吃透扩展kmp,每一步都可以对应到代码。如有不懂可以问本人。
刘琼雅ppt链接在文末。
下面贴码:
#include<iostream> #include<cstring> using namespace std; const int MM=100005; int next[MM],extand[MM]; char S[MM],T[MM]; void GetNext(const char *T) { int len = strlen(T),a = 0; next[0] = len; while(a < len - 1 && T[a] == T[a + 1]) a++; next[1] = a; a = 1; for(int k = 2; k < len; k ++) { int p = a + next[a] - 1,L = next[k - a]; if( (k - 1) + L >= p) { int j = (p - k + 1) > 0 ? (p - k + 1) : 0; while(k + j < len && T[k + j] == T[j]) j++; next[k] = j; a = k; } else next[k] = L; } } void GetExtand(const char *S,const char *T) { GetNext(T); int slen = strlen(S),tlen = strlen(T),a = 0; int MinLen = slen < tlen ? slen : tlen; while(a < MinLen && S[a] == T[a]) a++; extand[0] = a; a = 0; for(int k = 1; k < slen; k ++) { int p = a + extand[a] - 1, L = next[k - a]; if( (k - 1) + L >= p) { int j = (p - k + 1) > 0 ? (p - k + 1) : 0; while(k + j < slen && j < tlen && S[k + j] == T[j]) j ++; extand[k] = j; a = k; } else extand[k] = L; } } void show(const int *s,int len){ for(int i = 0; i < len; i ++) cout << s[i] << ' '; cout << endl; } int main() { while(cin >> S >> T) { GetExtand(S,T); show(next,strlen(T)); show(extand,strlen(S)); } return 0; }
http://wenku.baidu.com/view/fc9d8970f46527d3240ce072.html (刘琼雅扩展kmp ppt)