算法学习之KMP（模板整理）

2019-04-14 18:23发布

站内文章 / 模拟电子
17041 0 1584

一、学习记录

犹记当年学习C语言的字符串的时候那个悲情。。。 于是组队之后果断声明：鶸不玩字符串 然后将字符串丢给队友。。。 后来觉得吧，一些基础的东西还是要会的，比如KMP 粗浅的学了下KMP算法，也不敢瞎说什么，主要整理了下模板 学习记录： 主要看了刘大大的蓝书《算法竞赛入门经典--训练指南》 还有几篇博客：                            1. KMP算法详解
                           2.KMP算法详解                            3.KMP算法的一些题目

二、两种模板

初期使用的模板： #define mem(a,x) memset(a,x,sizeof(a)) #include using namespace std; typedef long long ll; const int N = 100000; /* KMP 算法模板 时间复杂度 ： O(n+m) [其中 n,m 是两字符串的长度] 说明： 1. a是长串 s是短串 即 a.size >= s.size 2.实现了“查找第一次匹配的位置” “匹配的次数” “记录所有匹配区间”三个功能 3.三个功能的实现代码非常相似,第3个功能可以同时实现前2个的功能 */ struct KMP { int f[N + 7]; void getfill (string s) //预处理 { memset (f, 0, sizeof (f) ); //根据其前一个字母得到 for (int i = 1; i < s.size(); i++) { int j = f[i]; while (j && s[i] != s[j]) j = f[j]; f[i + 1] = (s[i] == s[j]) ? j + 1 : 0; } } int finds (string a, string s) //找到第一次匹配的位置 a.size >= s.size { getfill (s); int j = 0; for (int i = 0; i < a.size(); i++) { while (j && a[i] != s[j]) j = f[j]; if (a[i] == s[j]) j++; if (j == s.size() ) { return i - s.size() + 1; //返回小串在大串中第一次出现的位置 } } return -1;//不匹配返回-1 } int findtimes(string a,string s)//返回匹配次数 { getfill(s); int j = 0;int times = 0; for (int i = 0;i < a.size();++i) { while (j&&a[i] != s[j]) j = f[j]; if (a[i] ==s[j]) j++; if (j == s.size()) { times++; } } return times;//不匹配的times将是0 } struct Interval { int l,r; }q[N];//记录所有匹配区间 [指在长串中的下标，下标从0开始] int t;//记录匹配次数 void findinterval(string a,string s)//找到并记录所有的匹配区间 { getfill(s); int j = 0;t = 0; for (int i = 0;i < a.size();++i) { while (j&&a[i]!=s[j]) j = f[j]; if (a[i] == s[j]) j++; if (j == s.size()) { t++; q[t].l = i - s.size() + 1; q[t].r = i; } } } void Print()//第3种功能附带打印功能 { cout<<"两串匹配了 "<< t <<"次,分别是 ："<> a >> s) { kmp.findinterval(a,s); kmp.Print(); } return 0; }



















后期的模板： #define mem(a,x) memset(a,x,sizeof(a)) #include using namespace std; typedef long long ll; const int N = 1000007; struct KMP { string s, t; //s.size > t.size int slen, tlen; int nx[N]; KMP (string s = "", string t = "") : s (s), t (t) //构造函数 { slen = s.size(); tlen = t.size(); mem (nx, 0); } void init (string s, string t) { this->s = s; this->t = t; slen = s.size(); tlen = t.size(); mem (nx, 0); } void getnx() { int i = 0, k = -1; nx[0] = -1; while (i < tlen) { if (k == -1 || t[i] == t[k]) nx[++i] = ++k; else k = nx[k]; } } int findindex() //返回首次出现的位置 { int i = 0, j = 0; getnx(); while (i < slen&&j < tlen) { if (j == -1||s[i] == t[j]) ++i,++j; else j = nx[j]; } if (j == tlen) return i - tlen; else return -1;//不匹配 } int findtimes()//返回出现次数 { if (slen == 1&&tlen == 1) { return s[0] == t[0]; } getnx(); int times = 0; for (int i = 0,j = 0;i < slen;++i) { while (j > 0&&s[i]!=s[j]) j = nx[j]; if (s[i] == t[j]) ++j; if (j == tlen) { ++times; j = nx[j]; } } return times; } }; int main() { return 0; }

三、关于next的感受心得

个人以为，KMP的精髓就在伟大的getnext的预处理里，（或者说在神奇的next数组里） getnext是对模式串进行预处理，而完全不涉及主串 getnext中其实是字符串自己和自己匹配， 关于next数组，他的意义不限于KMP算法，他可以找到字符串的循环节，他有很多独特的性质（很有用） 这里随意测试了2个性质 #define mem(a,x) memset(a,x,sizeof(a)) #include #include #include #include #include #include #include #include #include #include #include #include #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%lld",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%lld %lld",&x,&y) #define Pint(x) printf("%d",x) #define Pll(x) printf("%lld",x) #define Pintl(x) printf("%d ",x) using namespace std; typedef long long ll; const int N = 1000007; int nx[N]; char s[N]; void getnx() { int len = strlen(s); int i = 0,k = -1; nx[0] = -1; while (i < len) { if (k == -1||s[i] == s[k]) nx[++i] = ++k; else k = nx[k]; } } /* 结论 1 : 如果 len-next[len] 能被 len 整除 则 len - next[len] 是该串的循环节 */ /* int main() { while (~scanf("%s",s)) { if (s[0] == '.') break; getnx(); int len = strlen(s); if (len%(len-nx[len]) == 0) { //Pintl((len-nx[len]));//所以这个是循环节的长度 Pintl(len/(len-nx[len]));//这个是循环节的次数 } else puts("1"); } return 0; } */ /* 结论 2 ： s[0] ~ s[next[len]-1] 中的内容一定能与 s[len-next[len]] ~ s[len-1] 匹配 */ int main() { while (~scanf("%s",s)) { getnx(); int len = strlen(s); for (int i = 0;i < nx[len];++i) { putchar(s[i]); } cout</*     结论 3 ：         s[0] ~ s[next[i]-1] 中的内容一定能与 s[i-next[i]] ~ s[i-1] 匹配 */

四、针对next的应用

裸的KMP也有几道入门题，HDU 1711   POJ 3461(直接套模板即可) 另外关于next的性质的两道题： POJ 2406 利用next数组找字符串的循环节 #define mem(a,x) memset(a,x,sizeof(a)) #include #include #include #include #include #include #include #include #include #include #include #include #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%lld",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%lld %lld",&x,&y) #define Pint(x) printf("%d",x) #define Pll(x) printf("%lld",x) #define Pintl(x) printf("%d ",x) using namespace std; typedef long long ll; /* 结论：如果有一个字符串s,长度是len,它的失败函数是next， 如果len能被len-next[len]整除， 那么len-next[len]就是我们要求的那个子串的长度， 与之对应的字符串，就是我们想得到的子串 */ const int N = 1000007; int nx[N]; char s[N]; void getnx() { int len = strlen(s); int i = 0,k = -1; nx[0] = -1; while (i < len) { if (k == -1||s[i] == s[k]) nx[++i] = ++k; else k = nx[k]; } } int main() { while (~scanf("%s",s)) { if (s[0] == '.') break; getnx(); int len = strlen(s); if (len%(len-nx[len]) == 0) { //Pintl((len-nx[len]));//所以这个是循环节的长度 Pintl(len/(len-nx[len]));//这个是循环节的次数 } else puts("1"); } return 0; }
POJ 2752
又是利用了next数组的性质 #define mem(a,x) memset(a,x,sizeof(a)) #include #include #include #include #include #include #include #include #include #include #include #include #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%lld",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%lld %lld",&x,&y) #define Pint(x) printf("%d",x) #define Pll(x) printf("%lld",x) #define Pintl(x) printf("%d ",x) using namespace std; typedef long long ll; /* 从n - 1位既最后一位开始回滚， 若s[next[n-1]] == s[n-1]， 则子串s[0,1,2,...,next[n-1]]是满足条件的子串。 然后判断s[next[next[n-1]]] == s[n-1]是否成立， 这样一直回滚，直到next[next[.....next[n-1]]] == -1为止。 */ const int N = 400007; int nx[N]; char s[N]; int len; void getnx() { int i = 0,k = -1; nx[0] = -1; while (i < len) { if (k == -1||s[i] == s[k]) nx[++i] = ++k; else k = nx[k]; } } int main() { while(~scanf("%s",s)) { len = strlen(s); getnx(); int p = nx[len-1]; vectorr; while (p+1) { if (s[p] == s[len-1]) r.push_back(p+1); p = nx[p]; } for(int i = r.size()-1;i >= 0;--i) { Pint(r[i]);putchar(' '); } Pintl(len); } return 0; }

五、总结

1.KMP算法本身可能并没有特别的吸引我，但是那个神奇的next数组再次让本鶸见识到算法的伟大之处 鶸看别人写好的文章都不是很懂，简直不造那些前人是怎么想出来这么精妙的方法的（膜拜~~~~） 2.字符串的算法不仅仅限于字符串，在做一些关于数列的题的时候也可能用到字符串的算法 3.据说KMP和Trie过了就是AC自动机了，想当初第一次听到这个名字的时候还以为AC自动机 是指可以在比赛中自动AC（Accepted）的算法。。。囧~~~

热门文章