串的模式匹配

时间:2023-02-23 11:49:30

一、KMP算法的思想

D.E.KnuthJ.H.MorrisV.R.Pratt共同提出了一个改进算法,消除了Brute-Force算法中串s指针的回溯,完成串的模式匹配。时间复杂度为O(s.curlen+t.curlen)这就是Knuth-Morris-Pratt算法,简称KMP 算法。

1KMP算法形成过程:

S[i]P[j] ,为使主串指针 i不回溯,可以从模式串的第k个字符开始比较,即让 j重新赋值kk值如何确定?

S[i]P[j] j重新赋值为 k,必有:P1P2 …..Pk -1=Si -k +1 Si -k +2 ……Si -1.

同样必有:Pj -k+1Pj -k+2 ……Pj -1= Si -k +1 Si -k +2 ……Si -1.因此Pj -k+1Pj -k+2 ……Pj -1= P1P2 …..Pk -1.

串的模式匹配

串的模式匹配串的模式匹配

2KMP算法的基本思想:

        设目标串为s,模式串为t

         ij 分别为指示st的指针,ij的初值均为0

        若有 si = tj,则ij分别增1;否则,i不变,j退回至j=next[j]的位置 ( 也可理解为串s不动,模式串t向右移动到sitnext[j]对齐 )

        比较sitj。若相等则指针各增1;否则 j 再退回到下一个j=next[j]的位置(即模式串继续向右移动 ),再比较 sitj

   依次类推,直到下列两种情况之一:

   1)j退回到某个j=next[j]时有 si = tj,则指针各增1,继续匹配;

   2)j退回至 j=-1,此时令指针各增l,即下一次比较 si+1 t0

3next[j]的求法

   由定义: next[0]=-1

   next[j]= k,则有P0P1P2 …..Pk -1= Pj -kPj -k+2 ……Pj -1. next[j+1]=          

      1) Pk=Pj,必有P0P1P2 …..Pk -1Pk= Pj -kPj -k+2 ……Pj -1Pj,因此 next[j+1]=k+1=next[j]+1;

2)  PkPj,则P0P1P2 …..Pk -1PkPj -kPj -k+2 ……Pj -1Pj.在当前匹配的过程中,已有P0P1P2 …..Pk -1= Pj -kPj -k+2 ……Pj -1。若PkPj,应将模式向右滑动至以模式中的next[j]= k个字符和主串中的第j个字符相比较。若  k’=next[k],Pk’Pj,则说明存在一个长度为k’的子串相等:

        P0P1P2 …..Pk’ -1= Pj –k’Pj –k’+2 ……Pj -1且满足: 0<k’<k<j;  Pk’= Pj

此时有:next[j+1]=k’+1=next[k]+1

       3)否则 Pk’Pj:继续重复该过程。若k’=0:则令next[j+1]=0 .( k’=0,next(k’)=-1).
串的模式匹配

二、、KMP算法的C语言描述

串的模式匹配

串的模式匹配

三、KMP算法的C语言实现

  1 #include "stdio.h"
  2 
  3 #include "stdlib.h"
  4 
  5 #include "string.h"
  6 
  7 #include "ctype.h"
  8 
  9 #define OK 1
 10 
 11 #define ERROR 0
 12 
 13 typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
 14 
 15 typedef int Boolean; // Boolean是布尔类型,其值是TRUE或false
 16 
 17 #define N 16 // 数据元素个数
 18 
 19 #define MAXKEYLEN 16 // 关键字的最大长度
 20 
 21 #define STACK_INIT_SIZE 10 // 存储空间初始分配量
 22 
 23 #define STACKINCREMENT 2 // 存储空间分配增量
 24 
 25 typedef struct
 26 
 27 {
 28 
 29 char *ch;
 30 
 31 int length;
 32 
 33 }HString;
 34 
 35 void InitString(HString &T)
 36 
 37  { // 初始化(产生空串)字符串T
 38 
 39    T.length=0;
 40 
 41    T.ch=NULL;
 42 
 43  }//InitString
 44 
 45 int StrAssign(HString &T,char *chars)
 46 
 47 {// 生成一个其值等于串常量chars的串T
 48 
 49 int i,j;
 50 
 51 if(T.ch)
 52 
 53        free(T.ch); //释放T原有空间
 54 
 55 i=strlen(chars);//求chars的长度i
 56 
 57 if(!i)
 58 
 59    {//chars的长度为0
 60 
 61     T.ch=NULL;
 62 
 63        T.length=0;
 64 
 65    }//if
 66 
 67 else
 68 
 69    {
 70 
 71     T.ch=(char*)malloc(i*sizeof(char));//分配串空间
 72 
 73        if(!T.ch) exit(-1); //失败
 74 
 75        for(j=0;j<i;j++)
 76 
 77               T.ch[j]=chars[j];
 78 
 79        T.length=i;
 80 
 81    }//else
 82 
 83 return OK;
 84 
 85 }//StrAssign
 86 
 87 void StrPrint(HString &T)
 88 
 89 {
 90 
 91 int i;
 92 
 93 for(i=0;i<T.length;i++)
 94 
 95        printf("%c",T.ch[i]);
 96 
 97 printf("\n");
 98 
 99 }//StrPrint
100 
101 void get_next(HString T,int next[])
102 
103  { // 求模式串T的next函数修正值并存入数组next
104 
105    int i=1,j=0;
106 
107    next[0]=-1;
108 
109    while(i<T.length)
110 
111      if(j==-1||T.ch[i]==T.ch[j])
112 
113      {
114 
115        ++i;
116 
117        ++j;
118 
119           next[i]=j;
120 
121         }//if
122 
123        else j=next[j];
124 
125  }//get_next
126 
127 int Index_KMP(HString S,HString T,int pos,int next[])
128 
129  { // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。
130 
131    // 其中,T非空,1≤pos≤StrLength(S)
132 
133    int i=pos,j=0;
134 
135    while(i<S.length&&j<T.length)
136 
137      if(j==-1||S.ch[i]==T.ch[j]) // 继续比较后继字符
138 
139      {
140 
141        ++i;
142 
143        ++j;
144 
145      }
146 
147      else // 模式串向右移动
148 
149        j=next[j];
150 
151    if(j>=T.length) // 匹配成功
152 
153      return i-T.length;
154 
155    else
156 
157      return 0;
158 
159  }//Index_KMP
160 
161 void OutprintS(HString &t)
162 
163 {
164 
165 printf("串t为: ");
166 
167 StrPrint(t);
168 
169 }//OutprintS
170 
171 void InputS(HString &s)
172 
173 {
174 
175 char ch[80];
176 
177 printf("input the String:\n");
178 
179 scanf("%s",ch);
180 
181 StrAssign(s,ch);
182 
183 }//InputS
184 
185 int main()
186 
187 {
188 
189 int i,pos=1,p[N];
190 
191 HString t,s;
192 
193 InitString(s);//由于HSring定义了指针,所以必须初始化
194 
195 InitString(t);
196 
197 InputS(s);
198 
199 InputS(t);
200 
201 OutprintS(s);
202 
203 OutprintS(t);
204 
205 get_next(t,p);
206 
207 i=Index_KMP(s,t,pos,p);
208 
209 printf("主串和子串在第%d个字符处首次匹配\n",i+1);
210 
211 return 1;
212 
213 }    

 

六、next[j]求法的改进

Brute-Force算法的时间复杂度为O(n*m),但是实际执行近似于O(n+m)KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下,才会比BF算法快。KMP算法的最大特点是主串的指针不需要回溯,整个匹配过程中,过主串仅需从头到尾扫描一次,对于处理从外设输入的庞大文件很有效,可以边读边匹配。

串的模式匹配

串的模式匹配

文章转自:http://blog.163.com/zhoumhan_0351/blog/static/399542272009102981350695/