KMP算法应用举例
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了KMP算法应用举例,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含16307字,纯文字阅读大概需要24分钟。
内容图文
![KMP算法应用举例](/upload/InfoBanner/zyjiaocheng/1072/521dbca742d7442ca03a882bf020cdb3.jpg)
KMP是字符串匹配的经典算法
也是众多字符串基础的重中之重
A.
题意:给T组数据,每组有长度为n和m的母串和模式串。判断模式串是否是母串的子串,如果是输出最先匹配完成的位置,否则输出-1.
做法:直接套用模板。把char改成int。kmp函数中在模式串遍历到结尾的时候return,若没遍历到结尾,也就是不是子串返回-1
1 [cpp] view plain copy 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5usingnamespace std; 6int nexta[10005],a[1000005],s[10005]; 7int n,m; 8void getnexta(int s[]) 9{ 10 memset(nexta,0,sizeof(nexta)); 11int k = -1,j = 0; 12 nexta[0] = -1; 1314while(j < n ) 15 { 1617if(k == -1 || s[k] == s[j]) 18 { 19 nexta[j + 1] = k + 1; 20 j ++; 21 k ++; 22 } 23else24 { 25 k = nexta[k]; 26 } 27 } 2829} 30int kmp(int s[],int t[])//t模式串,s母串 31{ 32 getnexta(t); 3334int i = 0,j = 0; 35while(i < n && j < m) 36 { 37if(j == -1 || s[i] == t[j]) 38 { 39 i ++; 40 j ++; 41 } 42else43 { 44 j = nexta[j]; 45 } 46if(j == m) 47 { 48return i - j+ 1; 49 } 50 } 51return -1; 52} 53int main() 54{ 55// freopen("in.txt","r",stdin); 56int T; 57 scanf("%d",&T); 58while(T--) 59 { 60 scanf("%d%d",&n,&m); 61for(int i = 0;i < n; i ++) 62 { 63 scanf("%d",&a[i]); 64 } 65for(int j = 0; j < m;j ++) 66 { 67 scanf("%d",&s[j]); 68 } 69 printf("%d\n",kmp(a,s)); 70 } 71return0; 72 }
B.
题意:给T组数据,每组有两个字符串按顺序分别为模式串和母串。判断模式串在母串中出现的次数。模式串在母串中是可以相互覆盖的。
做法:直接套用模板。在kmp中当j==m也就是模式串完全匹配时,ans++,且j = nexta[j]
1 [cpp] view plain copy 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5usingnamespace std; 6int nexta[1000006]; 7char t[1000006],s[1000006]; 8void getnexta(char s[]) 9{ 10 memset(nexta,0,sizeof(nexta)); 11int n = strlen(s); 12int k = -1,j = 0; 13 nexta[0] = -1; 14while(j < n ) 15 { 1617if(k == -1 || s[k] == s[j]) 18 { 19 nexta[j + 1] = k + 1; 20 j ++; 21 k ++; 22 } 23else24 { 25 k = nexta[k]; 26 } 27 } 2829} 30int kmp(char s[],char t[])//t模式串,s母串.此种为返回首次匹配的位置,不能匹配则返回-1. 31{ 32 getnexta(t); 33int ans = 0; 34int n = strlen(s),m = strlen(t); 35int i = 0,j = 0; 36while(i < n && j < m) 37 { 38if(j == -1 || s[i] == t[j]) 39 { 40 i ++; 41 j ++; 42 } 43else44 { 45 j = nexta[j]; 46 } 47if(j == m)//根据题目要求改变 48 { 49 ans ++; 50 j = nexta[j]; 51 } 52 } 53return ans; 54} 55int main() 56{ 57// freopen("in.txt","r",stdin); 58int T; 59 scanf("%d",&T); 60while(T--) 61 { 62 scanf("%s%s",t,s); 63 printf("%d\n",kmp(s,t)); 64 } 65return0; 66 }
C.
题意:输入母串和模式串,以’#‘为结束。剪纸花,从母串中减去模式串问能剪出多少。这就意味着求解模式串的数量时不能重叠覆盖
做法:模板。在kmp中当j==m也就是模式串完全匹配时,ans++,且j = 0.要再次从头开始匹配
1 [cpp] view plain copy 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5usingnamespace std; 6int nexta[1006]; 7char t[1006],s[1006]; 8void getnexta(char s[]) 9{ 10 memset(nexta,0,sizeof(nexta)); 11int n = strlen(s); 12int k = -1,j = 0; 13 nexta[0] = -1; 14while(j < n ) 15 { 1617if(k == -1 || s[k] == s[j]) 18 { 19 nexta[j + 1] = k + 1; 20 j ++; 21 k ++; 22 } 23else24 { 25 k = nexta[k]; 26 } 27 } 2829} 30int kmp(char s[],char t[])//t模式串,s母串.此种为返回首次匹配的位置,不能匹配则返回-1. 31{ 32 getnexta(t); 33int ans = 0; 34int n = strlen(s),m = strlen(t); 35int i = 0,j = 0; 36while(i < n && j < m) 37 { 38if(j == -1 || s[i] == t[j]) 39 { 40 i ++; 41 j ++; 42 } 43else44 { 45 j = nexta[j]; 46 } 47if(j == m)//根据题目要求改变 48 { 49 ans ++; 50 j = 0; 51 } 52 } 53return ans; 54} 55int main() 56{ 57// freopen("in.txt","r",stdin); 58while(1) 59 { 60 scanf("%s",s); 61if(strcmp(s,"#") == 0) 62break; 63 scanf("%s",t); 64 printf("%d\n",kmp(s,t)); 65 } 66return0; 67 }
D.
题意:给T组数据,每组有一个字符串,只能在字符串的前面和后面增加字符,不能再中间增加,求要使这个字符串是周期循环的且周期的次数大于一,至少需要增加的字符数量。注意这个字符串是个手链,也就是说是增加字符后首位相连是周期的即可
做法:首先求最小循序节,考虑一种特殊情况就是nexta[n] = 0,这个时候前缀没有匹配后缀的地方,所以需要增加n个字符。求出最小循环节:n - nexta[n]。当n整除循环节时候,这时字符串已经是周期循环。当不整除时,最小循序节减去已经在字符串中的字符数目及ans = temp - (n % temp);(temp为最小循环节)
1 [cpp] view plain copy 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5usingnamespace std; 6int nexta[100005]; 7char s[100005]; 8void getnexta(char s[]) 9{ 10 memset(nexta,0,sizeof(nexta)); 11int n = strlen(s); 12int k = -1,j = 0; 13 nexta[0] = -1; 14while(j < n ) 15 { 16if(k == -1 || s[k] == s[j]) 17 { 18 nexta[j + 1] = k + 1; 19 j ++; 20 k ++; 21 } 22else23 { 24 k = nexta[k]; 25 } 26 } 27} 28int main() 29{ 30// freopen("in.txt","r",stdin); 31int T,ans,n,temp; 32 scanf("%d",&T); 33while(T --) 34 { 35 scanf("%s",s); 36 n = strlen(s); 37 getnexta(s); 38 temp = n - nexta[n];//最小循环节 39if(temp == n) 40 { 41 ans = n; 42 } 43elseif(n % temp == 0) 44 { 45 ans = 0; 46 } 47else48 { 49 ans = temp - (n % temp); 50 } 51 printf("%d\n",ans); 52 } 53return0; 54 }
E.
题意:给字符串的长度和一个字符串。读到eof。求每个字符串中在i之前的位置是循环的且次数大于1,求这个位置i以及循环的次数
做法:求每个位置i的最小循环节,判断是否整除和个数大于1,并用除法的值求次数
1 [cpp] view plain copy 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5usingnamespace std; 6int nexta[1000002]; 7char s[1000002]; 8int n; 9void getnexta() 10{ 11 memset(nexta,0,sizeof(nexta)); 12int k = -1,j = 0; 13 nexta[0] = -1; 14while(j < n ) 15 { 1617if(k == -1 || s[k] == s[j]) 18 { 19 nexta[j + 1] = k + 1; 20 j ++; 21 k ++; 22 } 23else24 { 25 k = nexta[k]; 26 } 27 } 2829} 30int main() 31{ 32// freopen("in.txt","r",stdin); 33int t = 0,temp; 34while(1) 35 { 36 t ++; 37 scanf("%d",&n); 38if(n == 0) 39break; 40 scanf("%s",s); 41 printf("Test case #%d\n",t); 42 getnexta(); 43for(int i = 1; i <= n; i ++) 44 { 45//cout<<nexta[i]<<" "; 46//cout<<f[i]<<endl; 47if(nexta[i] == 0) 48 { 49continue; 50 } 51else52 { 53 temp = i - nexta[i] ;//循环小节的长度 54if((i ) % temp == 0 && (i ) / temp > 1)//这是由于nexta[i]表示的是i-1 55 printf("%d %d\n",i ,(i ) / temp); 56 } 5758 } 59 printf("\n"); 60 } 61return0; 62} 6364/*65a a b a a b a a b a a b 66-1 0 1 0 1 2 3 4 5 6 7 8 670 1 2 3 4 5 6 7 8 9 10 11 68*/
F.
题意:每组给一个字符串,一直读到eof。这个字符串是重复写的AAAAAAA的一部分,求这个A最短是多少
做法:。。。。。。此题有问题,全网代码没有对的,我至少交了8+份代码
G.
题意:每组给以个字符串,一直读到‘.‘.字符串s = a^n,及都是由a构成的,求n的值
做法:求最小循环节,如果整除,那除得的数及为ans。如果不整除ans = 1
1 [cpp] view plain copy 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5usingnamespace std; 6int nexta[1000002]; 7char s[1000002]; 8int n; 9void getnexta() 10{ 11 memset(nexta,0,sizeof(nexta)); 12int k = -1,j = 0; 13 nexta[0] = -1; 14while(j < n ) 15 { 1617if(k == -1 || s[k] == s[j]) 18 { 19 nexta[j + 1] = k + 1; 20 j ++; 21 k ++; 22 } 23else24 { 25 k = nexta[k]; 26 } 27 } 2829} 30int main() 31{ 32//freopen("in.txt","r",stdin); 33int ans; 34while(1) 35 { 36 ans = 0; 37 scanf("%s",s); 38if(strcmp(s,".") == 0) 39break; 40 n = strlen(s); 41 getnexta(); 42if(n % (n - nexta[n]) == 0 ) 43 ans = n / (n - nexta[n]); 44else45 ans = 1; 46 printf("%d\n",ans); 47 } 48return0; 49} 505152//ababa
H.
题意:每组一个字符串,读到eof结束。寻找i使得字符串的前缀等于后缀
做法:首先n(字符串的长度)肯定是,因为此时前缀和后缀是一样的。对nexta[n]进行递归。及i= nexta[i].当nexta[i] == 0时结束。因为是nexta找到的所以以i为结束的字符串后缀等于以n为结束的字符串的后缀。可以看看kmp算法讲解中的图,体会一下
1 [cpp] view plain copy 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5usingnamespace std; 6int nexta[1000002]; 7char s[1000002]; 8int ans[1000002]; 9int n; 10void getnexta() 11{ 12 memset(nexta,0,sizeof(nexta)); 13int k = -1,j = 0; 14 nexta[0] = -1; 15while(j < n ) 16 { 1718if(k == -1 || s[k] == s[j]) 19 { 20 nexta[j + 1] = k + 1; 21 j ++; 22 k ++; 23 } 24else25 { 26 k = nexta[k]; 27 } 28 } 2930} 3132int main() 33{ 34//freopen("in.txt","r",stdin); 35int temp,k; 36while(scanf("%s",s) != EOF) 37 { 38 k = 0; 39if(strcmp(s,".") == 0) 40break; 41 n = strlen(s); 42 getnexta(); 43 temp = n; 44 ans[k] = n; 45 k ++; 46while(nexta[temp]!= -0) 47 { 48 temp = nexta[temp]; 49 ans[k] = temp; 50 k ++; 51 } 52for(int i = k -1; i > 0; i --) 53 printf("%d ",ans[i]); 54 printf("%d\n",ans[0]); 5556 } 57return0; 58} 596061//ababa
I.
题意:T组数据,每组m个DNA序列,每个DNA序列都有60个字符,且只由ACGT几个字母构成。判断m个DNA序列最长公共的子串是什么?如果有相同长度的公共子串,则输出字典序最小的。如果小于3输出“no ……”,大于等于3输出字符串
做法:对第一个DNA序列取从i开始到结尾的子串。与其他DNA序列进行匹配。因为是从前向后匹配,在kmp时做出改变,求出每个DNA序列和子串匹配的最长长度,再对所有最长长度取最短的那个。注意对长度相等时的处理。其中还用到strncpy,可以复制一定长度的字符串到指定字符串中。注意在最后加‘\0‘
1 [cpp] view plain copy 2 // 直接枚举第一串的所有后缀,然后与后面的所有串进行比较,判断有几个字母是相同的即可 3 #include <iostream> 4 #include <cstdio> 5 #include <cstring> 6 #include <algorithm> 7usingnamespace std; 8int nexta[100]; 9char c[12][100]; 10char s[100]; 11int n,m,l; 12void getnexta() 13{ 14 memset(nexta,0,sizeof(nexta)); 15int k = -1,j = 0; 16 nexta[0] = -1; 17while(j < n ) 18 { 19 20if(k == -1 || s[k] == s[j]) 21 { 22 nexta[j + 1] = k + 1; 23 j ++; 24 k ++; 25 } 26else 27 { 28 k = nexta[k]; 29 } 30 } 31 32} 33int kmp() 34{ 35int k = 0,j = -1; 36int maxx = 100,temp = 0; 37for(int i = 1 ;i < m; i ++) 38 { 39 temp = 0;j = 0,k = 0; 40while(j < l && k < 60) 41 { 42if(j == -1 || c[i][k] == s[j]) 43 { 44 j ++; 45 k ++; 46 47 } 48 49else 50 j = nexta[j]; 51if(j > temp)//每个DNA序列和子串匹配的最长长度 52 { 53 temp = j; 54 } 55 56 } 57if(temp < maxx)//所有DNA序列都和子串匹配的长度 58 maxx = temp; 59 } 60return maxx; 61} 62int main() 63{ 64//freopen("in.txt","r",stdin); 65int T,temp,num; 66 n = 60; 67 scanf("%d",&T); 68while(T--) 69 { 70char result[100]; 71char t[100]; 72 num = 0; 73 scanf("%d",&m); 74for(int i = 0; i < m; i ++) 75 { 76 scanf("%s",&c[i]); 77 } 78for(int i = 0; i < 58; i ++) 79 { 80 l = 60 - i; 81 strcpy(s,c[0] + i); 82 getnexta(); 83 temp = kmp(); 84if(num == temp) 85 { 86 strncpy(t,c[0] + i,temp); 87if(t < result) 88 { 89 strcpy(result,t); 90 } 91 t[temp] = ‘\0‘; 92 } 93elseif(num < temp) 94 { 95 strncpy(result,c[0] + i,temp); 96 result[temp] = ‘\0‘; 97 num = temp; 98 } 99 } 100//cout<<num<<endl; 101if(num >= 3) 102 { 103 printf("%s\n",result); 104// cout<<num<<endl; 105 } 106else107 printf("no significant commonalities\n"); 108 } 109return0; 110} 111112113//ababa
J.
题意:每组给两个字符串以eof结尾。求s1的前缀,等于s2后缀的长度.如果长度不是零空格之后输出相同的部分,否则只输出零即可
做法:把s2接在s1后面,求nexta[n].注意求得的ans长度不能大于s1或s2
1 [cpp] view plain copy 2 /* 考虑abcabcabcabc 3 abcabcabcabcabc这组数据也就是考虑当得数大于s1或s2时 4 */ 5 #include <iostream> 6 #include <cstdio> 7 #include <cstring> 8 #include <string> 9usingnamespace std; 10int nexta[100002]; 11char s[100002]; 12char a[50002]; 13int n; 14void getnexta() 15{ 16 memset(nexta,0,sizeof(nexta)); 17int k = -1,j = 0; 18 nexta[0] = -1; 19while(j < n ) 20 { 2122if(k == -1 || s[k] == s[j]) 23 { 24 nexta[j + 1] = k + 1; 25 j ++; 26 k ++; 27 } 28else29 { 30 k = nexta[k]; 31 } 32 } 3334} 35int main() 36{ 37// freopen("in.txt","r",stdin); 38while(scanf("%s%s",s,a) != EOF) 39 { 40int ans = 0; 41 strcat(s,a); 42int m = strlen(a); 43 n = strlen(s); 44 getnexta(); 45//cout<<s<<endl; 46//cout<<m<<endl; 47// cout<<n<<endl; 48 ans = nexta[n]; 49//cout<<n<<endl; 50if(ans != 0) 51 { 52if(ans > n || ans > m) 53 ans = min(n - m,m); 54for(int i = 0; i < ans; i ++) 55 printf("%c",s[i]); 56 printf(" %d\n",ans); 5758 } 59else60 printf("0\n"); 61 } 62return0; 63 }
K
题意:给T组数据,每组数据给一个长度为n的字符串s。求字符串每个前缀出现的次数,结果mod 10007
做法:dp[i]表示的是长度为i的字符串的前缀的个数。dp[i] = dp[nexta[i]] + 1。以i-1为结尾的后缀的个数是next[i],也是前缀的长度。这个前缀的长度中字符串本身的前缀出现的次数。因为以i - 1为后缀的字符串中都又出现了一次
ababa
dp[1] = 1 a
dp[2] = 1 ab
dp[3] = 2 aba a
dp[4] = 2 abab ab
dp[5] = 3 ababa aba a
1 [cpp] view plain copy 2 #include <iostream> 3 #include <cstdio> 4 #include <algorithm> 5 #include <list> 6 #include <map> 7 #include <stack> 8 #include <vector> 9 #include <cstring> 10 #include <sstream> 11 #include <string> 1213usingnamespace std; 14char s[200005]; 15int nexta[200005]; 16int dp[200005]; 17int n; 18void getnext() 19{ 20int j = 0,k = -1; 21 nexta[0] = -1; 22while(j < n) 23 { 24if(k == -1 || s[j] == s[k]) 25 { 26 nexta[j + 1] = k + 1; 27 j ++; 28 k ++; 29 } 30else31 { 32 k = nexta[k]; 33 } 3435 } 36} 37int main() 38{ 39//freopen("in.txt","r",stdin); 40int T,ans; 41 scanf("%d",&T); 42while(T--) 43 { 44 scanf("%d",&n); 45 scanf("%s",s); 46 getnext(); 47 memset(dp,0,sizeof(dp)); 48 ans = 0; 49for(int i = 1;i <= n; i ++) 50 { 51 dp[i] = dp[nexta[i]] + 1; 52 ans += dp[i] % 10007; 53 } 54 printf("%d\n",ans % 10007); 55 } 56return0; 57 }
L.
题意:给T组数据,每组数据第一行是26个字母表示[a,z]所对应的密文字母。第二行的字符串由两部分组成,第一部分是密文部分,第二部分是明文部分。明文部分可能是不完整的,也可能是完整的输出完整的明文部分
做法:先输出第二行的全部字符串。然后对整个字符串进行变化,把密文部分转化为明文部分。原串密文部分的长度一定大于等于明文部分。明文部分最长就是从整个字符串的一半开始的。将转化后的字符串与未转化之前的字符串的后半部分进行匹配。匹配到的返回结果就是原字符串中明文的个数:temp。则密文的个数为n - temp.实际应该的长度为2 * n - 2 * temp.应该输出的长度为:2 * n - 2 * temp - n.从转换后的字符串的temp位开始直接输出即可。从该位置开始到字符串的长度减去该位置都是待输出的不完整的字符串。其实质就是用完整的明文串,与题目中给出的不一定完整的明文串进行匹配。注意其中完整的是模式串,不完整的是所谓的母串。模式串是从头开始匹配的。而母串不是
提一下如何将密文转化为明文,将第一行该位置对应的字母转化为该位置i转化为字母(i + ‘a‘)
ps:这也就意味着,不要从头开始匹配,是母串。而普通kmp的模式串一定要是从头开始匹配的。
abcdefghijklmnopqrstuvwxyz
abcdab
abcdab
1 [cpp] view plain copy 2 // 密文和明文前后两端是重复的 3 #include <iostream> 4 #include <cstdio> 5 #include <algorithm> 6 #include <list> 7 #include <map> 8 #include <stack> 9 #include <vector> 10 #include <cstring> 11 #include <sstream> 12 #include <string> 1314usingnamespace std; 15 map<char,char>mapp; 16char s[100005]; 17char s2[100005]; 18int nexta[100005]; 19char c[30]; 20int n; 21void getnext() 22{ 23 memset(nexta,0,sizeof(nexta)); 24int j = 0,k = -1; 25 nexta[0] = -1; 26while(j < n) 27 { 28if(k == -1 || s[j] == s[k]) 29 { 30 nexta[j + 1] = k + 1; 31 j ++; 32 k ++; 33 } 34else35 { 36 k = nexta[k]; 37 } 3839 } 40} 41int kmp() 42{ 43int la = strlen(s2),lb = strlen(s); 44 getnext(); 45int i = 0, j = 0; 46while(i < la && j < lb) 47 { 48if(j == -1 || s2[i] == s[j]) 49 { 50 i ++; 51 j ++; 5253if(i == la) 54return j; 55 } 56else57 { 58 j = nexta[j]; 59 } 60 } 61return0; 62} 63int main() 64{ 65//freopen("in.txt","r",stdin); 66int T; 67 scanf("%d",&T); 68while(T--) 69 { 70 scanf("%s%s",c,s); 71 printf("%s",s); 72 n = strlen(s); 73int m = (n + 1) / 2; 74 strcpy(s2,s + m); 7576for(int i = 0; i < 26; i ++) 77 { 78 mapp[c[i]] = ‘a‘ + i; 79 } 80for(int i = 0; i < n; i ++) 81 { 82 s[i] = mapp[s[i]]; 83 } 84int temp = kmp(); 85// cout<<temp<<endl; 86for(int i =temp; i < n - temp; i ++)//n-temp密文长度 87 { 88 printf("%c",s[i]); 89 } 90 printf("\n"); 91 } 92return0; 93 }
Q.
题意:每组n个字符串,以eof结束。求每个字符串中满足S[i]=S[i+P] for i in [0..SIZE(S)-p-1],的位置。
做法:其实还是前缀与后缀相等,其中p是后缀开始的地方。递归nexta即可。因为nexta递归得到的以i为结束后缀等于前缀,等于整个长度的后缀.注意p的大小是n - nexta[n](nexta[n]是后缀的长度,n - nexta[n]就是后缀开始的位置了)
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4usingnamespace std; 5int nexta[1000005]; 6char s[1000005]; 7int ans[1000005]; 8int n; 9void getnexta() 10{ 11int j = 0,k = -1; 12 nexta[0] = -1; 13while(j < n) 14 { 15if(k == -1 || s[j] == s[k]) 16 { 17 nexta[j + 1] = k + 1; 18 j ++; 19 k ++; 20 } 21else22 { 23 k = nexta[k]; 24 } 25 } 26} 27int main() 28{ 29// freopen("in.txt","r",stdin);30int T; 31 scanf("%d",&T); 32for(int t=1; t<= T; t++) 33 { 34 scanf("%s",s); 35 n = strlen(s); 36 getnexta(); 37int a = n; 38int num = 0; 39while(nexta[a] != -1) 40 { 41 ans[num] = n - nexta[a]; 42 num ++; 43 a = nexta[a]; 44 } 45 printf("Case #%d: %d\n",t,num); 46for(int i = 0; i < num - 1; i ++) 47 { 48 printf("%d ",ans[i]); 49 } 50 printf("%d\n",ans[num - 1]); 51 } 52return0; 53 }
Z.
题意:n个字符串,每个字符串都可以写成EAEBE的形式,其中E可以为空,寻找最长的E
做法:首先我们很容易知道E最长长度为nexta[n],然后判断中间的那个E是否存在,设E的长度为i。从开头位置加1开始遍历(i+1),到<(n - i)为止,如果有next[j] == i那么可以判断这个长度的E存在。从E可能的最大长度开始遍历
1 [cpp] view plain copy 2 #include<iostream> 3 #include<cstring> 4 #include<stdio.h> 5usingnamespace std; 6char s[1000005]; 7char t[1000005]; 8int nexta[1000005]; 9int n; 10void getnexta() 11{ 12 memset(nexta,0,sizeof(nexta)); 13 nexta[0] = -1; 14int k = -1,j = 0; 15while(j < n) 16 { 17if(k == -1 || s[k] == s[j]) 18 { 19 nexta[j + 1] = k + 1; 20 j ++; 21 k ++; 22 } 23else24 k = nexta[k]; 25 } 26} 2728int main() 29{ 30// freopen("in.txt","r",stdin); 31int T; 32 scanf("%d",&T); 33while(T--) 34 { 35 scanf("%s",s); 36 n = strlen(s); 37 getnexta(); 38//cout<<nexta[n]<<endl; 39int ans = 0,i; 40bool flag ; 41for(i = min(n / 3 - 1,nexta[n] - 1);i >= 0;i --) 42 { 43//cout<<i<<endl; 44for(int j = i + 1; j < n - i; j ++) 45 { 46 flag = false; 47if(nexta[j] == i ) 48 { 49 ans = i + 1; 50 flag = true; 51break; 52 } 53 } 54if(flag) 55break; 56 } 57if(i == -1) 58 ans = 0; 59 cout<<ans<<endl; 60 } 61return0; 62 }
使用高级算法会减少思维难度,相比较来说,高级算法虽然难度大,但是实用性更强
原文:https://www.cnblogs.com/aininot260/p/9638097.html
内容总结
以上是互联网集市为您收集整理的KMP算法应用举例全部内容,希望文章能够帮你解决KMP算法应用举例所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。