分析不同网站的优缺点,网页设计产品介绍,建网站用什么系统好,泸州建设网站拓展kmp是对KMP算法的扩展#xff0c;它解决如下问题#xff1a; 定义母串S#xff0c;和字串T#xff0c;设S的长度为n#xff0c;T的长度为m#xff0c;求T与S的每一个后缀的最长公共前缀 其中next数组表示T[i,m-1]和T的最长公共前缀 1 const int maxn100010; //字符…拓展kmp是对KMP算法的扩展它解决如下问题 定义母串S和字串T设S的长度为nT的长度为m求T与S的每一个后缀的最长公共前缀 其中next数组表示T[i,m-1]和T的最长公共前缀 1 const int maxn100010; //字符串长度最大值2 int next[maxn],ex[maxn]; //ex数组即为extend数组3 //预处理计算next数组4 void GETNEXT(char *str)5 {6 int i0,j,po,lenstrlen(str);7 next[0]len;//初始化next[0]8 while(str[i]str[i1]i1len)//计算next[1]9 i;
10 next[1]i;
11 po1;//初始化po的位置
12 for(i2;ilen;i)
13 {
14 if(next[i-po]inext[po]po)//第一种情况可以直接得到next[i]的值
15 next[i]next[i-po];
16 else//第二种情况要继续匹配才能得到next[i]的值
17 {
18 jnext[po]po-i;
19 if(j0)j0;//如果iponext[po],则要从头开始匹配
20 while(ijlenstr[j]str[ji])//计算next[i]
21 j;
22 next[i]j;
23 poi;//更新po的位置
24 }
25 }
26 }
27 //计算extend数组
28 void EXKMP(char *s1,char *s2)
29 {
30 int i0,j,po,lenstrlen(s1),l2strlen(s2);
31 GETNEXT(s2);//计算子串的next数组
32 while(s1[i]s2[i]il2ilen)//计算ex[0]
33 i;
34 ex[0]i;
35 po0;//初始化po的位置
36 for(i1;ilen;i)
37 {
38 if(next[i-po]iex[po]po)//第一种情况直接可以得到ex[i]的值
39 ex[i]next[i-po];
40 else//第二种情况要继续匹配才能得到ex[i]的值
41 {
42 jex[po]po-i;
43 if(j0)j0;//如果iex[po]po则要从头开始匹配
44 while(ijlenjl2s1[ji]s2[j])//计算ex[i]
45 j;
46 ex[i]j;
47 poi;//更新po的位置
48 }
49 }
50 } 转载于:https://www.cnblogs.com/yZiii/p/7284660.html
