当前位置:首页 >> 学科竞赛 >>

KMP算法


字符串匹配问题KMP 【引例】给你两个字符串S和T,你需要回答,T串是否是S串的子串(即S串是否 包含T串)。 一、Brute-Force简称为BF算法,亦称简单匹配算法,其基本思路是: 从主串S="s1s2?sn"的第一个字符开始和模式串T="t1t2?tm"中的第一个字 符比较,若相等,则继续逐个比较后续字符;否则从主串S的第二个字符开

始重 新与模式串T的第一个字符进行比较。依次类推,若从模式串S的第i个字符开始, 每个字符依次和模式串T中的对应字符相等,则匹配成功,该算法返回i;否则, 匹配失败,函数返回0。 【算法框架】 int PiPei(string s,string t)//求模式串t在主串s中的位置 { i=1;j=1;//指针初始化 while(i<=lens&&j<=lent) if(s[i]==t[j]){i++;j++;}//继续比较后续字符 else{i=i-j+2;j=1;}//指针后退重新匹配 if(j>lent)return i-lent;else return 0; } 【复杂性分析】最好的情况下O(n+m),最坏情况为O(n*m) 例如:模式串为:‘00000001’ 主串为:‘000000000000000000000000000000000000000000001’ 二. 模式匹配的改进算法-KMP算法 KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算 法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了 某种程度的提高。 改进:每趟匹配过程中出现字符比较不等时,不回溯主指针i,利用已得到 的“部分匹配”结果将模式向右滑动尽可能远的一段距离,继续进行比较。 为此,定义P[j]函数,表明当模式中第j+1个字符与主串中相应字符i“失配”时, 在模式中需重新和主串中该字符进行比较的字符的位置。则有: 【KMP示例】: 【核心代码】: int KMP(string s,string t)//返回第一次匹配的位置 { int i,j,; j=0; //指针初始化 for(i=1;i<=lens;i++)//在主串中查找 { while(j>0&&t[j+1]!=s[i])j=P[j];//模式串向右滑动 if(t[j+1]==s[i])j++;//继续下一个字符的比较 if(j==lent)return i-lent+1;//{cout<<i-lent+1;j=P[j];} } return 0; }

【怎样求p[j]】 例如: void Get_next(string t)//注意字符串都是从1开始匹配 { int i,j; P[1]=0;j=0; for(i=2;i<=lent;i++) { while(j>0&&t[j+1]!=t[i])j=P[j];//向前寻找 if(t[j+1]==t[i])j++; P[i]=j; } } #include<iostream> #include<cstring> using namespace std; string s,t; int lens,lent,P[255];//前面最大匹配的定位 void Get_next(string t)//注意字符串都是从1开始匹配 { int i,j; P[1]=0;j=0; for(i=2;i<=lent;i++) { while(j>0&&t[j+1]!=t[i])j=P[j];//向前寻找 if(t[j+1]==t[i])j++; P[i]=j; } } int KMP(string s,string t)//返回第一次匹配的位置 { int i,j,; j=0; //指针初始化 for(i=1;i<=lens;i++)//在主串中查找 { while(j>0&&t[j+1]!=s[i])j=P[j];//模式串向右滑动 if(t[j+1]==s[i])j++;//继续下一个字符的比较 if(j==lent)return i-lent+1;//{cout<<i-lent+1;j=P[j];} } return 0; } int main() { cin>>s>>t; s=' '+s;lens=s.length()-1; t=' '+t;lent=t.length()-1; Get_next(t); //得到关于模式串t的next的值 cout<<KMP(s,t)<<endl; return 0;

} 附:网上讲义
KMP算法是拿来处理字符串匹配的。换句话说,给你两个字符串,你需要回答,B串是否 是A串的子串(A串是否包含B串) 。比如,字符串A="I'm matrix67",字符串B="matrix",我们 就说B是A的子串。你可以委婉地问你的MM:“假如你要向你喜欢的人表白的话,我的名字 是你的告白语中的子串吗?” 解决这类问题, 通常我们的方法是枚举从A串的什么位置起开始与B匹配, 然后验证是否匹 配。假如A串长度为n,B串长度为m,那么这种方法的复杂度是O (mn)的。虽然很多时候复 杂度达不到mn(验证时只看头一两个字母就发现不匹配了) ,但我们有许多“最坏情况”,比 如,A= "aaaaaaaaaaaaaaaaaaaaaaaaaab",B="aaaaaaaab"。我们将介绍的是一种最坏情况下 O(n)的算法(这里假设 m<=n) ,即传说中的KMP算法。 之所以叫做KMP,是因为这个算法是由Knuth、Morris、Pratt三个提出来的,取了这三个人 的名字的头一个字母。这时,或许你突然明白了AVL 树为什么叫AVL,或者Bellman-Ford为什 么中间是一杠不是一个点。 有时一个东西有七八个人研究过, 那怎么命名呢?通常这个东西 干脆就不用人名字命名了,免得发生争议,比如“3x+1问题”。扯远了。 个人认为KMP是最没有必要讲的东西,因为这个东西网上能找到很多资料。但网上的讲法 基本上都涉及到“移动(shift)”、“Next函数”等概念,这非常容易产生误解(至少一年半前我看 这些资料学习KMP时就没搞清楚) 。在这里,我换一种方法来解释KMP算法。 假如,A="abababaababacb",B="ababacb",我们来看看KMP是怎么工作的。我们用两个指 针i和j分别表示,A[i-j+ 1..i]与B[1..j]完全相等。也就是说,i是不断增加的,随着i的增加j相应 地变化,且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符(j当然越大越好) , 现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时,i和j各加一;什么时候j=m了,我们 就说B是A的子串(B串已经整完了) ,并且可以根据这时的i值算出匹配的位置。当 A[i+1]<>B[j+1],KMP的策略是调整j的位置(减小j值)使得A[i-j+1..i]与B[1..j]保持匹配且新的 B[j+1]恰好与A[i+1]匹配(从而使得i和j能继续增加) 。我们看一看当 i=j=5时的情况。 i = 1 2 3 4 5 6 7 8 9 ?? A=abababaabab ? B=ababacb j=1234567 此时,A[6]<>B[6]。这表明,此时j不能等于5了,我们要把j改成比它小的值j'。j'可能是多 少呢?仔细想一下,我们发现,j'必须要使得B[1..j]中的头j'个字母和末j'个字母完全相等(这 样j变成了j'后才能继续保持i和j的性质) 。这个j'当然要越大越好。在这里,B [1..5]="ababa", 头3个字母和末3个字母都是"aba"。而当新的j为3时,A[6]恰好和B[4]相等。于是,i变成了6, 而j则变成了 4: i = 1 2 3 4 5 6 7 8 9 ?? A=abababaabab ? B= ababacb j= 1234567

从上面的这个例子,我们可以看到,新的j可以取多少与i无关,只与B串有关。我们完全可 以预处理出这样一个数组P[j], 表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时, 新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。 再后来,A[7]=B[5],i和j又各增加1。这时,又出现了A[i+1]<>B[j+1]的情况: i = 1 2 3 4 5 6 7 8 9 ?? A=abababaabab ? B= ababacb j= 1234567 由于P[5]=3,因此新的j=3: i = 1 2 3 4 5 6 7 8 9 ?? A=abababaabab ? B= ababacb j= 1234567 这时,新的j=3仍然不能满足A[i+1]=B[j+1],此时我们再次减小j值,将j再次更新为P[3]: i = 1 2 3 4 5 6 7 8 9 ?? A=abababaabab ? B= ababacb j= 1234567 现在,i还是7,j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样,j必须减小到P[1], 即0: i = 1 2 3 4 5 6 7 8 9 ?? A=abababaabab ? B= ababacb j= 01234567 终于,A[8]=B[1],i变为8,j为1。事实上,有可能j到了0仍然不能满足A[i+1]=B[j+1](比如 A[8]="d"时) 。因此,准确的说法是,当j=0了时,我们增加i值但忽略j直到出现A[i]=B[1]为止。 这个过程的代码很短(真的很短) ,我们在这里给出:

【核心代码】: int KMP(string s,string t)//返回第一次匹配的位置,字符串从1开始 { int i,j,; j=0; //指针初始化 for(i=0;i<lens;i++)//在主串中查找 { while(j>0&&t[j+1]!=s[i])j=P[j];//模式串向右滑动 if(t[j+1]==s[i])j++;//继续下一个字符的比较 if(j==lent)return i-lent+1;//{cout<<i-lent+1;j=P[j];}

} return 0; }
最后的j=P[j]是为了让程序继续做下去,因为我们有可能找到多处匹配。 这个程序或许比想像中的要简单,因为对于i值的不断增加,代码用的是for循环。因此, 这个代码可以这样形象地理解:扫描字符串A,并更新可以匹配到B的什么位置。 现在,我们还遗留了两个重要的问题:一,为什么这个程序是线性的;二,如何快速预处 理P数组。 为什么这个程序是O(n)的?其实,主要的争议在于,while循环使得执行次数出现了不确定 因素。 我们将用到时间复杂度的摊还分析中的主要策略, 简单地说就是通过观察某一个变量 或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析 可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小(但 不能减成负的) ,而另外的改变j值的地方只有第五行。每次执行了这一行,j都只能加1;因 此,整个过程中j最多加了n个1。于是,j最多只有n次减小的机会(j值减小的次数当然不能 超过n,因为j永远是非负整数) 。这告诉我们,while循环总共最多执行了n次。按照摊还分析 的说法,平摊到每次for循环中后,一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这 样的分析对于后面P数组预处理的过程同样有效,同样可以得到预处理过程的复杂度为 O(m)。 预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通过P[1],P[2],...,P[j-1]的值 来获得P[j]的值。对于刚才的B="ababacb",假如我们已经求出了P[1],P[2],P[3]和P[4],看看我 们应该怎么求出P[5]和P[6]。P[4]=2,那么P [5]显然等于P[4]+1,因为由P[4]可以知道,B[1,2] 已经和B[3,4]相等了,现在又有B[3]=B[5],所以P[5]可以由P[4] 后面加一个字符得到。P[6]也 等于P[5]+1吗?显然不是,因为B[ P[5]+1 ]<>B[6]。那么,我们要考虑“退一步”了。我们考虑 P[6]是否有可能由P[5]的情况所包含的子串得到,即是否P[6]=P[ P[5] ]+1。这里想不通的话可 以仔细看一下: 1234567 B=ababacb P=00123? P[5]=3是因为B[1..3]和B[3..5]都是"aba";而P[3]=1则告诉我们,B[1]、B[3]和B[5]都是"a"。 既然P[6]不能由P[5]得到,或许可以由P[3]得到(如果B[2]恰好和B[6]相等的话,P[6]就等于 P[3]+1了) 。显然,P[6]也不能通过P[3]得到,因为B[2]<>B[6]。事实上,这样一直推到P[1]也 不行,最后,我们得到,P[6]=0。 怎么这个预处理过程跟前面的KMP主程序这么像呢?其实,KMP的预处理本身就是一个B 串“自我匹配”的过程。它的代码和上面的代码神似:

void Get_next(string t)//注意字符串都是从1开始匹配 { int i,j; P[1]=0;j=0; for(i=2;i<=lent;i++) { while(j>0&&t[j+1]!=t[i])j=P[j];//向前寻找

if(t[j+1]==t[i])j++; P[i]=j; } }
最后补充一点:由于KMP算法只预处理B串,因此这种算法很适合这样的问题:给定一个B 串和一群不同的A串,问B是哪些A串的子串。 串匹配是一个很有研究价值的问题。事实上,我们还有后缀树,自动机等很多方法,这些 算法都巧妙地运用了预处理.

【典型例题】 【例题1】Power Strings(PKU2406)2954 【问题描述】我们定义a*b为两个字符串a和b相连接,例如a = "abc" 和b="def", 那么a*b="abcdef"。也可以用幂运算来表示,如a^0="" (空串) ,a^(n+1)=a*(a^n)。 【输入格式】 多组测试数据, 每组测试数据一行仅一个字符串s, 长度不超过10^6。 文件最后一行为一个小数点作为结束标志。 【输出格式】对于每组测试数据输出一行为使得字符串s=a^n成立时,n的值。 【样例输入】
abcd aaaa ababab .

【样例输出】 1 4 3 【知识考点】KMP匹配 【题目大意】 给你N个字符串, 对于每个字符串,看其是由几个重复子串构成的, 例如,abcd,是由1个abcd构成的;aaaa,是由4个a构成的,ababab,是由3个ab 构成的。 【试题分析】根据P数组的性质,S[1..P[i]]=S[i-P[i]+1..i],也就是说S[P[Len]+1] 到S[Len]才有可能是该串的重复子串,所以如果Len% (Len-P[Len])=0,则代表 S[P[Len]+1]到S[Len]是重复子串,长度为Len/(Len-p[Len]);否则重复子串为S, 长度为1。 #include<iostream> #include<cstring> using namespace std;

const int maxn=1000005; string s;int p[maxn],len; void Get_next() { int i,j,t; p[1]=0;j=0; for(i=2;i<=len;i++)//预处理P数组 { while(j>0&&s[j+1]!=s[i])j=p[j]; if(s[j+1]==s[i])j++; p[i]=j; } } int main() { while(1) { cin>>s;s=' '+s;len=s.length()-1; if(s[1]=='.')break; Get_next(); int k=len-p[len]; if(len%k==0)cout<<len/k<<endl; else cout<<1<<endl; } return 0; } 【例题2】Period(PKU1961)2955
【问题描述】给你若干个字符串,对于每个字符串,分解成 N 个前缀子串。对于每个前缀 子串,看其是由几个重复子串构成的。也就是说,对于字符串 S 的前 i (2 <= i <= N)个字符能 否用子串 A 表示为 AK 的形式,要求计算子串 A 的长度和循环周期 k(k>1) 的值。例如 aabaabaab,前缀子串 aa,是由 2 个 a 构成的;前缀子串 aabaab,是由 2 个 aab 构成的,前 缀子串 aabaabaab 是由,3 个 aab 构成的。 【 输入 格圏】 输入 文件包 含多 组测试 数据, 每组 测试 数据共 计两行 ,行 为一 个整数 N(2,=N<=1000000),表示字符串 S 的长度,第二行为字符串 S,文件最后一行以一个 0 作为 结束。 【输出格式】对于每组测试数据,第一行输出"Test case #" 和该测试数据是第几组,接下来 若干行,每行为子串 A 的长度和循环周期 k (k>1)的值,按照前缀长度递增的顺序输出。每 组数据结束输出一空行。 【样例输入】 3 aaa 12 aabaabaabaab 0 【样例输出】 Test case #1 22 33

Test case #2 22 62 93 12 4

【知识考点?KMP匹配
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define Maxn 1000005 int N, P[Maxn]; char s[Maxn]; void KMP(int c) { scanf("%s",s+1); memset(P,0,sizeof(P)); P[1] = 0; for (int i=2, j=0; i<=N; i++) { while (j && s[j+1]!=s[i]) j = P[j]; if (s[j+1]==s[i]) j++; P[i] = j; } printf("Test case #%d\n",c); for (int i=2; i<=N; i++) if (P[i]) if (i%(i-P[i])==0) printf("%d %d\n",i,i/(i-P[i])); printf("\n"); } int main() { for (int i=1; ;i++) { scanf("%d",&N); if (!N) break; KMP(i); } getchar();getchar(); }

【例题 3】 】Seek the Name, Seek the Fame (PKU2752)2956 【问题描述】给你若干个字符串,求其前缀 = 后缀的长度,从小到大依次输出。例如 ababcabab,依次输出 2(ab) ,4(abab) ,9(ababcabab) 。 【输入格式】输入文件包含多组测试数据,每组数据为一行一个字符串 S,仅有小写字母组 成。1<=Length of S<=400000。 【输出格式】 对于每组测试数据输出一行按照长度递增的顺序输出。 【样例输入】 ababcababababcabab aaaaa 【样例输出】 2 4 9 18 12345

【知识考点?KMP匹配
#include <cstdio> #include <cstring> #define MaxN 400000 char s[MaxN+5]; int next[MaxN+5], n; void Kmp() { n = strlen(s); next[1] = 0; for (int i=2, j=0; i<=n; i++) { while (s[j]!=s[i-1] && j) j = next[j]; if (s[j]==s[i-1]) j++; next[i] = j; } return ; } int ans[MaxN+5]; void Output() { ans[0] = 0; for (int i=n; i; i=next[i]) ans[++ans[0]] = i; for (int i=ans[0]; i; i--) printf("%d ", ans[i]); return ; }

int main() { //freopen("a.in", "r", stdin); //freopen("a.out", "w", stdout); while (scanf("%s", s)!=EOF) { Kmp(); Output(); putchar('\n'); } return 0; }

【例题4】Oulipo(POJ3461) 3589 【问题描述】给出两个字符串,求出模式串? 在主串S中出现了多少次。 【输入格式】输入文件第一行一整数n,表示数据的组数。每组数据包含两題, 第一行为模式串T(1<=|T|<=10,00?),第二行为主串S(|T|<=|S|<=1,000,000),均由 大写字母组成。 【输出格式】输出文件为n行,每行一个整数表示每组数据中模式串T圠主串S中 出现的次数。 【样例输入】
3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN

【样例输出】 1 3 0


相关文章:
经典KMP算法(易理解)
经典KMP算法(易理解)_IT/计算机_专业资料。网上找的,很容易理解 KMP 算法小结 Posted on 2011/06/14 by huangchao 主要看了这里,感觉讲的十分的不错 感觉讲...
KMP算法详解
KMP算法详解。KMP 字符串模式匹配详解 KMP 字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高 效算法。简单匹配算法的时间复杂度为 O(m*n);KMP...
KMP算法详解
() 运行结果,如下图所示: 代码实现二: 再给出代码实现二之前,让我们再次回顾下关于 KMP 算法的第一篇文章中 的部分内容: “第二节、KMP 算法 2.1、 覆盖...
kmp算法详解
引记此前一天,一位 MS 的朋友邀我一起去与他讨论快速排序,红黑树,字典树,B 树、后 缀树, 包括 KMP 算法, 唯独在讲解 KMP 算法的时候, 言语磕磕碰碰, ...
Kmp算法详解
KMP 算法,是由 Knuth,Morris,Pratt 共同提出的模式匹配算法,其对于任何模式和目标序 列,都可以在线性时间内完成匹配查找,而不会发生退化,是一个非常优秀的模式...
数据结构-KMP算法的实现
13 参考文献 2 1 需求分析 1.1 问题描述 KMP 算法是对一般模式匹配算法的改进,由 D.E.Knuth 与 V.R.Pratt 和 J.H.Morris 同时发 现的因此人们称它为...
改进KMP算法
模式匹配的一种改进算法---KMP 算法 模式匹配的一种改进算法这种改进算法是 D.E.Knuth 与 V.R.Pratt 和 J.H.Morris 同时发现的,因此人们称它为 克努特-莫里...
详解KMP算法中Next数组的求法
详解KMP 算法中 Next 数组的求法 例如: 1 2 3 4 5 6 7 8 模式串 next 值 a b a a b c a c 0 1 1 2 2 3 1 2 next 数组的求解方法是:第...
BF算法与KMP算法
BF算法与KMP算法_计算机软件及应用_IT/计算机_专业资料。BF算法与KMP算法,附带运行结果1、问题一:【①问题描述】用 C++/C 编写程序实现 BF 算法,进行模式匹配。...
kmp算法求next 和nextval
kmp算法求next 和nextval_IT/计算机_专业资料。快速方便的掌握kmp算法中 next 和nextval的计算方法。数组值的求解方法。 next 数组值的求解方法 例如:模式串 next ...
更多相关标签:
kmp | kmp算法详解 | kmp算法next原理 | kmplayer | kmp算法next计算方法 | kmp算法时间复杂度 | 熊猫算法 | kmp算法代码 |