kmp算法例题

1、一个n×n的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为。

2、一个串的任意连续字符组成的子序列称为串的，该串称为。

3、串长度为0的串称为，只包含空格的串称为。

4、若两个串的长度相等且对应位置上的字符也相等，则称两个串。

5、寻找子串在主串中的位置，称为。

其中，子串又称为。

6、求出二维数组A[n,n]的两条对角线元素之和（程序题）。

基本知识字符串的操作C++中string类中相关操作的实现KMP矩阵压缩存储矩阵转置编程题1 、请编写一个函数，输入两个字符串，求他们的最长公共子序列。

例如：输入两个字符串ABCBDAB和BDCABA,字符序列BCBA和BDAB都是他们的最长公共子序列，则输出他们的长度4。

2 、给定一个源串和目标串，能够对串进行如下操作：（2012.Baidu、google）在给定位置上插入一个字符串。

替换任意字符删除任意字符使得源串等于目标串，源串和目标串的长度都小于2000。

求出相似度=（操作次数+1）/2。

注：距离=操作次数3、求数组的子数组之和的最大值。

4、递归（全排列）5、一个字符串中的任意一个子序列，若子序列中个字符值均相等，则称为字符平台。

写一算法，输入任意一字符串S，输出S中长度最大的所有字符平台的起始位置及所含字符。

注意：最大字符平台有可能不止一个。

例如：字符串“aabcbbbbdccccaaa”的最大字符平台是“bbbb”和“cccc”。

是第i行中值最小的元素，同时又是第j列中值最6、鞍点是指矩阵中的元素aij大的元素。

试设计一个算法求矩阵A的所有鞍点。

7、字符串反序。

c++实现KMP算法KMPKMP算法解决的问题字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中开始的位置。

如何做到时间复杂度O(N)完成？思路：⾸先判断两个字符串是否为空串，并且str2的长度是否⼩于str1的长度，因为题⽬要求str1中包含str2。

以上都满⾜的情况下，⾸先定义两个变量分别为 x ，y 作为后续字符串中字符遍历的下标，然后再⽣成⼀个vector容器next，⽤来后续的匹配加速然后在str2中，做加速操作，也就是看当前 i - 1和之前的所有字符，有没有相同的，最⼤匹配长度。

从上图可以看到，下标0和1位置的值永远都是固定的-1和0,。

x 字符是 i 位置，x 前⾯的 c 是 i - 1 位置，也就是从下标0位置到5位置，找最⼤的匹配长度，然后填到 i 的next中。

这是循环中的case1如果当next中的值⼤于0的时候，从b开始，找到next中的2位置，然后跳转到当前位置的next中的坐标上，接着进⾏匹配。

最后如果到next为0或者-1的位置上，就标记当前位置为0，然后到下⼀个坐标继续判断。

当 i 遍历完str2后，循环结束，代表next中的值已经全部设置好了。

当str1 和 str2 没有循环遍历到尾部的时候，只要 str1 中 x 的位置等于 str2 中 y 的位置，x 和 y 就同时⾃增。

如果next中的值等于 -1 ，就说没有匹配成功，x 单独⾃增。

让str1往后挪⼀位如果str2中的没有匹配成功，就往前找next数组的值，只要不等于 -1 ，就⼀直执⾏这个往前移的过程。

最后看 y 是否已经到了str2的位置，如果到了就说明找到了，直接返回 x的位置减去 y的位置，就是匹配开始的位置，否则就是没有找到，直接返回 -1void getNextArray(string str, vector<int>& next){if (str.length() == 1){next.push_back(-1);}next.resize(str.length());next[0] = -1;next[1] = 0;int i = 2;int cn = 0;while (i < next.size()){if (str[i - 1] == str[cn]){next[i++] = ++cn;}else if (cn > 0){cn = next[cn];}else {next[i++] = 0;}}}int getIndexOf(string s, string m){if (s == "" || m == "" || s.length() < 1 || s.length() < m.length()){return -1;}int x = 0;int y = 0;vector<int> next;getNextArray(m,next);while (x < s.length() && y < m.length()){if (s[x] == m[y]){x++;y++;}else if (next[y] == -1){x++;}else {y = next[y];}}return y == m.length() ? x - y : -1;}以上就是c++ 实现KMP算法的详细内容，更多关于c++ KMP算法的资料请关注其它相关⽂章！。

kmp算法python代码摘要：1.KMP 算法简介2.KMP 算法的Python 实现3.KMP 算法的应用示例正文：1.KMP 算法简介KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主字符串中查找一个子字符串出现的位置。

该算法的关键在于通过预处理子字符串，减少不必要的字符比较，从而提高匹配速度。

2.KMP 算法的Python 实现以下是KMP 算法的Python 实现：```pythondef compute_prefix_function(pattern):m = len(pattern)prefix_function = [0] * (m + 1)prefix_function[0] = 0i, j = 1, 0while i < m:if pattern[i] == pattern[j]:j += 1prefix_function[i] = ji += 1else:if j!= 0:j = prefix_function[j - 1]else:prefix_function[i] = 0i += 1return prefix_functiondef kmp_search(text, pattern):m, n = len(text), len(pattern)prefix_function = compute_prefix_function(pattern) i, j = 0, 0while i < m:if pattern[j] == text[i]:i += 1j += 1if j == n:return i - jelif i < m and pattern[j]!= text[i]:if j!= 0:j = prefix_function[j - 1]else:i += 1return -1if __name__ == "__main__":text = "我国是一个伟大的国家"pattern = "伟大的"result = kmp_search(text, pattern)if result!= -1:print("子字符串"{}" 在主字符串中第{} 位置出现。

KMP（模板）算法讲解：模板来源：⾸先：KMP的模板为：void get_next(char *a, int *nex) {nex[1] = 0;for (int i = 2, j = 0; i <= len; i++) {while (j > 0 && a[i] != a[j + 1])j = nex[j];if (a[i] == a[j + 1])j++;nex[i] = j;}return;}int KMP(char *a, char *b) {//b为母串for (int i = 1, j = 0; i <= strlen(b + 1); i++) {while (j > 0 && (j == strlen(a + 1) || b[i] != a[j + 1]))j = nex[j];if (b[i] == a[j + 1])j++;f[i] = j;//若a在b中出现,，返回出现的位置//if(f[i]==strlen(a+1)){return i-strlen(a);}}return1;}例题：题意：求字符串中的最短循环节，并输出该循环节KMP最⼩循环节、循环周期：定理：假设S的长度为len，则S存在最⼩循环节，循环节的长度L为len-next[len]，⼦串为S[0…len-next[len]-1]。

（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。

（2）如果不能，说明还需要再添加⼏个字母才能补全。

需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。

注意这⾥的len是原字符串的len+1；1 #include<cstdio>2 #include<string.h>3 #include<algorithm>4using namespace std;5int T, len;6char s[100000 + 5];7int nex[100000 + 5];89void get_next(char* p, int next[]){10int pLen = strlen(p) + 1;//要求循环节长度时这⾥才+111 next[0] = -1;12int k = -1;13int j = 0;14while (j < pLen - 1){15if (k == -1 || p[j] == p[k]){16 ++j;++k;17if (p[j] != p[k])18 next[j] = k;19else20 next[j] = next[k];21 }22else{23 k = next[k];24 }25 }26}2728int kmp(char* s, char* p){29int i = 0;30int j = 0;33while (i < sLen && j < pLen){34//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++35if (j == -1 || s[i] == p[j]){36 i++;37 j++;38 }39else{40//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j] 41//next[j]即为j所对应的next值42 j = nex[j];43 }44 }45if (j == pLen)46return i - j;47else48return -1;49}5051int main() {52 scanf("%d", &T);53while (T--) {54 memset(nex, 0, sizeof(nex));55 scanf("%d", &len);56 scanf("%s", s);57 len = strlen(s);58 get_next(s, nex);59 printf("%d\n", len - nex[len]);60for (int i = 0; i < len - nex[len]; i++)61 printf("%c", s[i]);62 printf("\n");63 }64return0;65 }（数字KMP）1 #include<cstdio>2 #include<string.h>3 #include<algorithm>4using namespace std;5int T, len;6int len1, len2;7int s1[1000000 + 5];8int s2[1000000 + 5];9int nex[1000000 + 5];1011void get_next(int* p, int next[]) {12int pLen = len2;//要求循环节长度时这⾥才+113 next[0] = -1;14int k = -1;15int j = 0;16while (j < pLen - 1) {17if (k == -1 || p[j] == p[k]) {18 ++j; ++k;19if (p[j] != p[k])20 next[j] = k;21else22 next[j] = next[k];23 }24else {25 k = next[k];26 }27 }28}2930int kmp(int* s, int* p) {31int i = 0;32int j = 0;35 get_next(s2, nex);36while (i < sLen && j < pLen) {37//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++38if (j == -1 || s[i] == p[j]) {39 i++;40 j++;41 }42else {43//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j] 44//next[j]即为j所对应的next值45 j = nex[j];46 }47 }48if (j == pLen)49return i - j;50else51return -1;52}5354int main() {55 scanf("%d", &T);56while (T--) {57 scanf("%d %d", &len1, &len2);58for (int i = 0; i < len1; i++)59 scanf("%d", &s1[i]);60for (int i = 0; i < len2; i++)61 scanf("%d", &s2[i]);62if (kmp(s1,s2) == -1)63 printf("-1\n");64else65 printf("%d\n", kmp(s1,s2)+1);66 }67return0;68 }。

KMP⼏道⼊门题⽬HDU 1711 Number Sequence（模板题）#include<stdio.h>#include<string>const int maxn=1e6+10;const int maxm=1e4+10;int t,n,m,s[maxn],p[maxn];int next[maxm];void GetNext(){int plen=0;int slen=-1;next[0]=-1;while(plen<m){if(slen==-1||p[plen]==p[slen]){plen++;slen++;if(p[plen]!=p[slen])next[plen]=slen;else next[plen]=next[slen];}else slen=next[slen];}}int kmp(){int plen=0;int slen=0;while(plen<m&&slen<n){if(plen==-1||p[plen]==s[slen]){plen++;slen++;}else plen=next[plen];}if(plen==m)return slen-plen+1;else return -1;}int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&s[i]);for(int i=0;i<m;i++)scanf("%d",&p[i]);GetNext();printf("%d\n",kmp());}return0;}View CodeHDU 2087 剪花布条求⼀个串在另⼀个串中的出现次数，KMP模板题#include<iostream>#include<string>using namespace std;string s,p;int plen,slen,Next[1010];void GetNext(){int j=0;int k=-1;Next[0]=-1;while(j<plen){if(k==-1||p[j]==p[k]){j++;k++;if(p[j]!=p[k])Next[j]=k;else Next[j]=Next[k];}else k=Next[k];}}int kmp(){int j=0;int i=0;int count=0;while(j<plen&&i<slen){if(j==-1||p[j]==s[i]){j++;i++;}else j=Next[j];if(j==plen){j=0;count++;}}return count;}int main(){while(cin>>s&&s[0]!='#'){cin>>p;plen=p.size();slen=s.size();GetNext();printf("%d\n",kmp());}return0;}View CodeHDU 2594 Simpsons’ Hidden Talents （next函数应⽤）#include<iostream>#include<string.h>using namespace std;const int maxn=5e5+10;char s1[maxn],s2[maxn];int Next[maxn],len1,len2,ans;void GetNext(){int k=-1;int j=0;Next[0]=-1;while(j<len1+len2){if(k==-1||s1[j]==s1[k]){j++;k++;Next[j]=k;}else k=Next[k];}}int main(){while(~scanf("%s%s",s1,s2)){len1=strlen(s1);len2=strlen(s2);strcat(s1,s2);GetNext();ans=Next[len1+len2];while(ans>len1||ans>len2)ans=Next[ans];if(ans){for(int i=0;i<ans;i++)printf("%c",s1[i]);printf(" %d",ans);printf("\n"); }else printf("%d\n",ans);}return0;}View Code。

KMP（模板）kmp算法是解决单模匹配问题的算法，难点在于求next[]数组求next[]数组：对于⼦串的所有前缀⼦串的最长公共前后缀的长度，就是next[]数组的值⾸先，要了解两个概念："前缀"和"后缀"。

"前缀"指除了最后⼀个字符以外，⼀个字符串的全部头部组合；"后缀"指除了第⼀个字符以外，⼀个字符串的全部尾部组合。

如下图所⽰：下⾯再以”ABCDABD”为例，进⾏介绍：”A”的前缀和后缀都为空集，共有元素的长度为0；”AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

eg:主串为cbbbaababac ⼦串为ababac初始化next[0]=-1;⼦串的最长公共前后缀长度a -->0 next[1]=0 a的前缀为空，后缀也为空，共有元素的长度为0ab -->0 next[2]=0 ab前缀为[a]，后缀为[b]，共有元素的长度为0aba -->1 next[3]=1 前缀为[a，ab]，后缀为[a，ba]，共有元素的长度为1abab -->2 next[4]=2 前缀为[a，ab，aba]，后缀为[b，ab，bab]，共有元素的长度为2 ababa -->3 next[5]=3 前缀为[a,ab,aba,abab]，后缀也为[a,ba,aba,baba]，共有元素的长度为3next[i]数组的作⽤是在当⼦串字母s[i]在和主串字母p[j]失配的时候,next[i]数组提供⼀个值，⼦串整体移动( i-next[i] )个位置，继续⽤s[next[i]]去和主字母p[j]匹配eg:模板串是cbbbaababac，⼦串是ababa⼦串下标： 0 1 2 3 4a b a b a失配跳转位置next[]： -1 0 0 1 2这⾥解释⼀下：当⼦串和主串失配的时候,就根据next[]的值移动⼦串到相应位置去和主串匹配。

扩展KMP题⽬hdu4333/*题意：字符串s[0..n-1]，每次把最后⼀个字符放到前⾯，求形成的字符串⽐最初串分别⼩，相同，⼤于的个数因为是为了练习扩展KMP所以肯定是扩展KMP，为了循环⽅便，在后⾯复制字符串，求出next[]数组后，如果next[i]>n那么肯定相等，如果⼩于就判断s[ next[i] ]和 s[ i+next[i] ]的⼤⼩判断trick：题⽬求得是形成的不同的字符串的个数，可以知道相等的字符串肯定只有⼀个，⽽从0..n-1,第⼆个next[i]⼤于n那么这个i就是该字符串的循环节；*/#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<cmath>#include<vector>#include<algorithm>using namespace std;const int N=100000+10;char s[N*2];int next[N*2],n;void getNext(char *s,int next[]){int nn=strlen(s);next[0]=nn;int p=0;while (s[p+1] && s[p]==s[p+1]) p++;next[1]=p;int k=1;for (int i=2;i<nn;i++){int p=k+next[k]-1, L=next[i-k];if (i+L<=p) next[i]=L;else{int j=p-i+1;if (j<0) j=0;while (i+j<nn && s[i+j]==s[j]) j++;next[i]=j; k=i;}}}void work(){int ret1,ret2,ret3;ret1=ret2=ret3=0;getNext(s,next);for (int i=0;i<n;i++){if (i!=0 && next[i]>=n) break;if (next[i]<n) {if (s[ i+next[i] ]<s[ next[i] ]) ret1++;else ret3++;}else ret2++;}printf("%d %d %d\n",ret1,ret2,ret3);}int main(){int T,cas=0;scanf("%d",&T);while (T--){scanf("%s",s);printf("Case %d: ",++cas);n=strlen(s);for (int i=0;i<n;i++){s[n+i]=s[i];}s[n+n]='\0';// cout<<s<<endl;work();}return0;}hdu36131/*2题意：将⼀个串分成俩个串，如果是回⽂串值就是所有字符的值，如果不是值就为03问你最⼤的值是多少；45分析：因为是扩展KMP的题，很容易想到⽤扩展KMP判读是否是回⽂串，⽽且题⽬的6特点是⾄少有⼀端是端点，这很容易想到前缀和后缀，然后思路就出来了；7⾸先将串s逆转变成s1，求出s的所有后缀与s1的最长公共⼦串的长度，8这样分割成两段的后⾯⼀段，判断该段是否是回⽂只要判断最长长度是否等于后⾯⼀段的长度就可以了了 9前⾯⼀段类似，只是要求出s1的所有后缀与s的最长公共⼦串的长度,判断⽅法类似101112*/13 #include<cstdio>14 #include<cstring>15 #include<cstdlib>16 #include<iostream>17 #include<algorithm>18 #include<cmath>19 #include<vector>20using namespace std;21const int N=500000+10;22char s[N],s1[N];23int v[30];24int ext1[N],ext2[N],next[N];25void getNext(char *s,int next[]){26int nn=strlen(s);27 next[0]=nn;28int p=0;29while (s[p+1] && s[p]==s[p+1]) p++;30 next[1]=p;31int k=1, L;32for (int i=2;i<nn;i++){33 p=k+next[k]-1; L=next[i-k];34if (i+L<=p) next[i]=L;35else {36int j=p-i+1;37if (j<0) j=0;38while (i+j<nn && s[i+j]==s[j]) j++;39 next[i]=j; k=i;40 }41 }4243 }44void getExtend(char *s,char *T,int *ext){45 getNext(s,next);46int p=0, nn=strlen(s);47while (s[p] && s[p]==T[p]) p++;48 ext[0]=p;49int k=0, L;50for (int i=1;i<nn;i++){51 p=k+ext[k]-1; L=next[i-k];52if (i+L<=p) ext[i]=L;53else {54int j=p-i+1;55if(j<0) j=0;56while (i+j<nn && s[i+j]==T[j]) j++;57 ext[i]=j; k=i;58 }59 }60 }61int val[N];62void work(){63 memset(val,0,sizeof(val));64int len=strlen(s);65for (int i=0;i<len;i++) val[i+1]=val[i]+v[s[i]-'a'];66676869for (int i=len-1;i>=0;i--) s1[len-i-1]=s[i];70 s1[len]='\0';71// cout<<s<<endl<<s1<<endl;72 getExtend(s1,s,ext1);73 getExtend(s,s1,ext2);7475int ret=0;76for (int i=1;i<len;i++){77int l1=i,l2=len-l1;78int tmp=0;79if (ext1[len-i]==l1) tmp+=val[i];80if (ext2[i]==l2) tmp+=val[len]-val[i];81if (tmp>ret) ret=tmp;82 }83 printf("%d\n",ret);84 }85int main(){86int T;scanf("%d",&T);87while (T--){88for (int i=0;i<26;i++) scanf("%d",v+i);89 scanf("%s",s);90 work();91 }92return0;93 }94/*954961 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 197aaadbbbd981 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 199ab1001 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1101aba1021 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1103aaaaaaaaaaaaaaa104105*/poj16991/*2题意：给你n个串，求最短的串使得n个串都包含在⾥⾯（n<=10） 3从n的数据范围就可以看出状态压缩dp4dp[i][j]表⽰已经包含了"i"个串，且最后⼀个串是j的最⼩长度5预处理出s[i]的后缀与s[j]的前缀的最长公共⼦串67*/8 #include<cstdio>9 #include<cstring>10 #include<iostream>11 #include<cmath>12 #include<vector>13 #include<algorithm>14using namespace std;15const int N=20+10;16char s[N][N];17int n,next[N],mz[N][N],ext[N];18void getNext(char *s,int *next){19int nn=strlen(s);20 next[0]=nn;21int p=0;22while (s[p+1] && s[p]==s[p+1]) p++;23 next[1]=p;24int k=1, L;25for (int i=2;i<nn;i++){26 p=k+next[k]-1; L=next[i-k];27if (i+L<=p) next[i]=L;28else{29int j=p-i+1;30if (j<0) j=0;31while (i+j<nn && s[i+j]==s[j]) j++;32 next[i]=j; k=i;33 }34 }35 }36void getExtend(char *s,char *T,int ext[]){37 getNext(s,next);38int nn=strlen(s);39int p=0;40while (s[p] && T[p] && s[p]==T[p]) p++;41 ext[0]=p;42int k=0,L;43for (int i=1;i<nn;i++){44 p=k+ext[k]-1; L=next[i-k];45if (i+L<=p) ext[i]=L;46else {47int j=p-i+1;48if (j<0) j=0;49while (i+j<nn && s[i+j]==T[j]) j++;50 ext[i]=j; k=i;51 }52 }53 }54void init(){55 memset(mz,0,sizeof(mz));56for (int i=0;i<n;i++){57for (int j=0;j<n;j++){58if (i==j) continue;59 getExtend(s[i],s[j],ext);60int nn=strlen(s[i]);61for (int k=0;k<nn;k++){62if (ext[k]==nn-k) {63 mz[i][j]=nn-k; break;64 }65 }66 }67 }68/*for (int i=0;i<n;i++){69 for (int j=0;j<n;j++){70 cout<<mz[i][j]<<" ";71 }cout<<endl;72 }*/73 }74const int NN=1<<10;75int dp[NN][10];76void Min(int &x,int y){77if (x==-1) x=y;78else x=min(x,y);79 }80void work(){81 memset(dp,-1,sizeof(dp));82for (int i=0;i<n;i++){83 dp[1<<i][i]=strlen(s[i]);84 }85for (int i=0;i<(1<<n);i++){86for (int j=0;j<n;j++){87if (dp[i][j]==-1) continue;88for (int k=0;k<n;k++){89if ( i&(1<<k) ) continue;90 Min(dp[i^(1<<k)][k],dp[i][j]+strlen(s[k])-mz[j][k]);91 }92 }93 }94int ret=-1;95for (int i=0;i<n;i++){96 Min(ret,dp[(1<<n)-1][i]);97 }98 cout<<ret<<endl;99100 }101int main(){102int T;scanf("%d",&T);103while (T--){104 scanf("%d",&n);105for (int i=0;i<n;i++) scanf("%s",s[i]);106 init();107 work();108 }109return0;110 }。