KMP算法--字符串模式匹配算法

来源:转载

今天看到第四章《串》了,其中我觉得花的时间多一点的值得我写篇随笔的知识点就是:4.3 串的模式匹配算法;书上介绍了两种字符串匹配算法,一种是最简单最容易想到的逐个字符匹配算法(时间复杂度在好的情况下为O(n+m),[n为原串,m为匹配串],在最坏的情况下为O(n*m)),这个在我的代码中有了,就不赘述了。另外一种就是KMP算法,话说是三个人同时想到的算法,这仨名字各取开头的字符就是这个算法的名称了。这个算法是模式匹配的改进算法;(时间复杂度为O(m))。

逐个字符匹配算法
 1 int indexOf(string s,string t,int pos){//逐个字符匹配算法,从s串的pos位置开始,返回t出现的首位置
2 if(t.empty()){//字串不要为空
3 return -1;
4 }
5 int i = pos;
6 int temp = 0;
7 for(;i<s.size();i++){
8 temp = i;
9 for(int j = 0;j<t.size();j++){
10 if(s[temp] == t[j]){//如果相等,就继续循环下去
11 temp++;
12 if(j == (t.size()-1)){
13 return i;//返回出现的首位置
14 }
15 }else{//不相等
16 break;
17 }
18 }
19 }
20 }

而这个KMP算法在大体思想就是这样:

注意: s为原串,t为模式串,即小一点的那个,后面都是一样。↑↓

        ↓i=0 从这儿开始比较

1.s : a c a b a a b a a b c a c a a b c

   t : a b a a b c a c (红色为t在s中第一次出现)

 ↑j=0   next[0]=-1 (next[]数组的作用等会儿说哈)

 

          ↓i=1

2.s : a c a b a a b a a b c a c a a b c

   t : a b a a b c a c

   ↑j=1   next[1]=0   (发现c!=b,所以t串又要从头来比较,后面的代码就如下,j = next[j];  if(j==-1){j=0;)


          ↓i=1

3.s : a c a b a a b a a b c a c a a b c

   t :    a b a a b c a c

   ↑j=1   next[1]=0  (发现c!=a,所以s串又要后退点了)


             ↓i=2

4.s : a c a b a a b a a b c a c a a b c

   t :      a b a a b c a c

      ↑j=0   next[0]=-1  (相等,好的继续)


                          ↓i=7

5.s : a c a b a a b a a b c a c a a b c

   t :      a b a a b c a c

                   ↑j=5   next[5]=2  (发现c!=a了,这时候就是体现算法的时候了,此时i会暂停向后移动,而t串应该从哪里开始比较呢?next数组告诉了我们答案,从t[2]开始和s串i位置开始比较,如下图)


                          ↓i=7

6.s : a c a b a a b a a b c a c a a b c

   t :              a b a a b c a c

                   ↑j=2   next[2]=0  (后面的移动方式我没必要画了,很明显已经移到合适的地方了,乍一看很巧,细细一想还是很有智慧的)


 好,我来说说上面出现的每个参数的作用吧:s为原串,t为模式串,i为s串的移动指针,j为t串的移动指针,next数组的作用是指明t串指针j的位置的,也就是j回溯多少,当S串中的第i个字符与t串中的第j个字符不等时,s串的第i个字符(i指针永远不会往回走,最多只是暂停下)应该与模式中的哪个字符再比较的。针对每个t串,都会生成相对应的next数组,而next如何生成?

请看next特征数组构造:

    模式串t开头的任意个字符,把它称为前缀子串,如t0t1t2…tm-1。在t的第i位置的左边,取出k个字符,称为i位置的左子串,即ti-k+1... ti-2 ti-1 ti。求出最长的(最大的k)使得前缀子串与左子串相匹配称为,在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征数n[i]特征数组成的向量称为该模式串的特征向量。
   可以证明对于任意的模式串t = t0t1…tm-1,确实存在一个由模式串本身唯一确定的与目标串无关的数组next,计算方法为:
   (1)  求t0…ti-1中最大相同的前缀和后缀的长度k;
   (2)  next[i] = k;

   作为特殊情况,当i=0时,令next[i] = -1;显然,对于任意i(0≤i<m),有next[i] < i;假定已经计算得到next[i], 那么next[i+1] = ? 特征数ni ( -1≤ ni ≤ i )是递归定义的,定义如下:
   (1) n[0] = -1,对于i > 0的n[i] ,假定已知前一位置的特征数 n[i-1]= k ;
   (2) 如果ti = tk ,则n[i] = k+1 ;
   (3) 当ti ≠ tk 且k≠0时,则令k = n [k -1] ; 让(3)循环直到条件不满足;
   (4) 当qi ≠ qk 且k = 0时,则ni = 0;

   根据以上分析,可以得到next特征数组的计算方法,算法代码如下:

 1 void getNext(string t,int* next){//求子字串t的next[]函数之并存入数组中
2 int temp = 0;
3 int zm = 0;
4 for(int i = 0; i < t.size();i++){//从0开始循环
5 temp = i-1;
6 if(i == 0){//第一个的时候,为-1
7 next[i] = -1;
8 }else if(temp > 0){
9 for(int j = temp;j>0;j--){
10 if(equals(t,i,j)){
11 next[i] = j;
12 break;
13 }else{
14 next[i] = 0;//视为其他情况为0
15 continue;
16 }
17
18 }
19 }else{
20 next[i] = 0;//其他情况为0
21 }
22
23 }
24
25 }
26
27 bool equals(string t,int i,int j){//比较字符串t[0]~t[j-1]同t[i-j]~t[j]是否相等
28 int temp = i-j;
29 //if((j-1)==(2*j-i)){//如果长度相同
30 for(int k = 0; k < j; k++,temp++){
31 if(t[k]!=t[temp]){//如果有不相同的,返回false
32 return false;
33 }
34 }
35 return true;//运行到这儿说明字符串t[0]~t[j-1]同t[i-j]~t[j]相等
36 }

  到这里了,解决了一个点了,还有一个点就是,i串既然不回溯,还是有暂停的,至于暂停总是有这样规律的:第一不匹配--停,第二次不匹配--走...针对i串的同一个字符没有第三次哦,为什么?你懂的。

说到这儿,我想KMP算法的思想应该讲完了,看起来KMP算法是要好些,通常来说,模式串t的长度比S串的小的多,对于整个匹配算法来讲,确实要改进不少,虽然第一种算法的时间复杂度是O(n*m),但是在一般的情况下,其实际执行的时间按近似于O(n+m),所以至今很多地方也有采用;

总结:KMP算法在模式串t与主串s存在许多“部分匹配”的情况下才显得速度很快,这个算法的最大特点就是,主串的指针不需要回溯,从头扫一遍就行了,这对处理庞大的数据文件很有效,也可以边读入便匹配,无需回头再重读。

忘记贴代码了,呵呵,补上:

 1 /*
2 2011-7-25 zhangming
3 第四章,串 4.3节-串的模式匹配算法
4 总的来说有两种算法,
5 1,逐个字符匹配算法;(此匹配算法最简单,时间复杂度在好的情况下为O(n+m),[n为原串,m为匹配串],在最坏的情况下为O(n*m))
6 2,KMP算法;模式匹配的改进算法;(时间复杂度为O(m))
7 */
8 #include <iostream>
9 #include <string>
10 using namespace std;
11 int indexOf(string s,string t,int pos);//逐个字符匹配算法,从s串的pos位置开始,返回t出现的首位置
12 int indexOfKMP(string s,string t,int pos);//KMP算法;模式匹配的改进算法;
13 void getNext(string t,int* next);//求子字串t的next函数之并存入数组中
14 bool equals(string t,int i,int j);//比较字符串t[0]~t[j-1]同t[i-j]~t[j]是否相等
15 void main(){
16 string s = "acabaabaabcacaabc";
17 string t = "abaabcac";
18 cout<<t<<"出现在"<<s<<"的第"<<indexOf(s,t,2)+1<<"位置。/n";
19 cout<<t<<"出现在"<<s<<"的第"<<indexOfKMP(s,t,2)+1<<"位置。/n";
20 system("pause");
21 }
22
23 int indexOf(string s,string t,int pos){//逐个字符匹配算法,从s串的pos位置开始,返回t出现的首位置
24 if(t.empty()){//字串不要为空
25 return -1;
26 }
27 int i = pos;
28 int temp = 0;
29 for(;i<s.size();i++){
30 temp = i;
31 for(int j = 0;j<t.size();j++){
32 if(s[temp] == t[j]){//如果相等,就继续循环下去
33 temp++;
34 if(j == (t.size()-1)){
35 return i;//返回出现的首位置
36 }
37 }else{//不相等
38 break;
39 }
40 }
41 }
42 }
43 int indexOfKMP(string s,string t,int pos){//KMP算法;模式匹配的改进算法;
44 if(t.empty()){//t字串不要为空
45 return -1;
46 }
47 int* next = new int[t.size()];
48 int pause = 0;//控制是否暂停的
49 getNext(t,next);
50 int i = 0,j = 0;
51 while(i!=s.size()){
52 if(s[i]==t[j]){
53 i++;
54 j++;
55 }else{
56 if(pause==1){//如果不需要暂停
57 pause=0;
58 i++;
59 }else{//如果需要暂停
60 pause=1;
61 }
62 j = next[j];
63 if(j==-1){
64 j=0;
65 }
66 }
67 if(j==t.size()){
68 return i-t.size();
69 }
70 }
71 return -1;
72 }
73 void getNext(string t,int* next){//求子字串t的next[]函数之并存入数组中
74 int temp = 0;
75 int zm = 0;
76 for(int i = 0; i < t.size();i++){//从0开始循环
77 temp = i-1;
78 if(i == 0){//第一个的时候,为-1
79 next[i] = -1;
80 }else if(temp > 0){
81 for(int j = temp;j>0;j--){
82 if(equals(t,i,j)){
83 next[i] = j;
84 break;
85 }else{
86 next[i] = 0;//视为其他情况为0
87 continue;
88 }
89
90 }
91 }else{
92 next[i] = 0;//其他情况为0
93 }
94
95 }
96
97 }
98 bool equals(string t,int i,int j){//比较字符串t[0]~t[j-1]同t[i-j]~t[j]是否相等
99 int temp = i-j;
100 //if((j-1)==(2*j-i)){//如果长度相同
101 for(int k = 0; k < j; k++,temp++){
102 if(t[k]!=t[temp]){//如果有不相同的,返回false
103 return false;
104 }
105 }
106 return true;//运行到这儿说明字符串t[0]~t[j-1]同t[i-j]~t[j]相等
107 }


分享给朋友:
您可能感兴趣的文章:
随机阅读: