前言:2019.7.23,复习kmp算法.
1.关于字符串匹配.
Q:给定字符串a,字符串b,问a是否在b中出现?出现多少次?出现在b的什么位置?在未学kmp之前,对于第一问我想到的是tire树查看,但2,3问tire树显然力不从心.暴力? o(n^4)的两两子串匹配?显然不行.这时就需要更高级的算法kmp.
2.kmp算法导入.
我们想想暴力究竟暴力在哪里?当我们用匹配串t去匹配主串s时一但匹配失败时，我们会从头枚举s对于t的开头再进行一次匹配.显然这样我们会对一些已经匹配好的状态重新清零,不能加以利用.例如: 对于主串S: a a a b a a a g t ... 匹配串 T: a a a b a a a j k, 显然我们在第一次暴力匹配S的'g'与T的'j'失配时,第二次匹配时我们会选择从S的第二个a开始匹配,显然我们可以直接让T的前3个a与S后3个a匹配可以简化到最优枚举,kmp就利用这一点优于暴力.
3.kmp算法.
1.nxt 数组 .
我们定义nxt[ i ] = k表示字符串t[ 0 ]..t[ k-1]与t[ i -k ]..t[ i-1 ] 一一匹配,其中k为所有可满足字符串前缀等于后缀中长度中的最大长度.怎么求?显然nxt[ 0 ] nxt[ 1 ] nxt[ 2 ]...nxt[ i] nxt[i+1]存在关系.我们设nxt[ i ] = g ,即为t[ 0 ]...t [ g-1] 与 t [ i-g ]..t[ i-1]一一匹配,当s[ g ]==s[ i ]时,显然nxt[ i+1 ]=g+1,当这时s[ g ] ! = s[ i ]时,我们将g = nxt[ g ] 就可以得到此时第二长的最长前缀等于后缀的长度 g' ( 证明可先假设 g' 为此时第二长的最长前缀等于后缀,再画图反证. ),再看s[ g ']是否等于 s [ i ] ? 等于 则 s[ i+1]=s [ g'],否则就 g''=nxt[ g' ],得到第三长的最长前缀等于后缀的长度 g'',类推即可.最坏情况我们推至g=nxt[0]=-1(初始化) , 直接退出循环,s[i+1 ]=g+1=0,即不存在.code:
1 void getnext() 2 { 3 int k=-1,i=0; 4 nxt[0]=-1; 5 while(i<lent){ 6 while(k>=0&&t[k]!=t[i]) 7 k=nxt[k]; 8 i++,k++; 9 nxt[i]=k; 10 } 11 }
2.利用nxt数组优化字符串匹配.对于主串S,匹配串T,用 j 表示在S上的位置,用 i 表示在 T 上的位置.用两层while,第一层while限制j<lens,第二层while尝试用 i 去匹配 j,当匹配成功时++i,++j,未匹配成功时就令i = nxt[ i ], 以减小匹配带来的不必要的枚举.当 i = =lent时则代表匹配成功,可令i = nxt [ i ] 进行反复匹配.这样我们知道了 T 在 S 上出现了多少次即出现的位置. code:
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 #define e exit(0) 6 #define R register 7 const int maxn=1e6+10; 8 char s[maxn],t[maxn]; 9 int lens,lent,deep,nxt[maxn],pos[maxn]; 10 void getnext() 11 { 12 int k=-1,i=0; 13 nxt[0]=-1; 14 while(i<lent){ 15 while(k>=0&&t[k]!=t[i]) 16 k=nxt[k]; 17 i++,k++; 18 nxt[i]=k; 19 } 20 } 21 void kmp() 22 { 23 int i=0,j=0; 24 while(j<lens){ 25 while(i>=0&&t[i]!=s[j]) 26 i=nxt[i]; 27 i++,j++; 28 if(i==lent){ 29 pos[++deep]=j-lent+1; 30 } 31 } 32 } 33 int main() 34 { 35 // freopen("s.in","r",stdin); 36 // freopen("s.out","w",stdout); 37 scanf("%s",s),scanf("%s",t); 38 lens=strlen(s),lent=strlen(t); 39 getnext(); 40 kmp(); 41 for(R int i=1;i<=deep;++i) 42 printf("%d ",pos[i]); 43 for(R int i=1;i<=lent;++i) 44 printf("%d ",nxt[i]); 45 return 0; 46 }