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、字符串反序。

在生物信息学中的应用
在生物信息学中，KMP算法被广泛应用于基因序列的比对和拼接，以及蛋白质序列 的匹配和比对。
通过构建基因序列或蛋白质序列的索引表，KMP算法可以在O(n+m)的时间复杂度 内完成序列的比对和拼接，提高了比对和拼接的准确性和效率。
KMP算法在生物信息学中的应用有助于深入了解基因和蛋白质的结构和功能，为生 物医学研究和疾病诊断提供了有力支持。
06 实验总结与展望
KMP算法的优缺点
优点
高效：KMP算法在匹配失败时能跳过 尽可能多的字符，减少比较次数，从
而提高匹配效率。
适用范围广：KMP算法适用于各种模 式串匹配问题，不受模式串长度的限 制。
缺点
计算量大：KMP算法需要计算和存储 部分匹配表，对于较长的模式串，计 算量较大。
不适合处理大量数据：KMP算法在处 理大量数据时可能会占用较多内存， 导致性能下降。
匹配失败的处理
当模式串中的某个字符与主串中的对应字符不匹配时，模式串向右 滑动，与主串的下一个字符重新对齐，继续比较
next[ j]表示当模式串中第j个字符与主 串中的对应字符不匹配时，模式串需 要向右滑动的位置。
next数组的构建
next数组的作用
在匹配过程中，通过next数组可以快 速确定模式串需要滑动到哪个位置， 从而提高了匹配效率。
通过已知的next值，递推计算出next 数组中其他位置的值。
KMP算法的时间复杂度
01
02
03
04
时间复杂度分析
KMP算法的时间复杂度取决 于模式串在主串中出现的次数 以及每次匹配所花费的时间。
最佳情况
当模式串在主串中连续出现时 ，KMP算法的时间复杂度为

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 }。

如何求解next[]数组 如何求解next[]数组 next[]
还剩下一个问题：next[]这个辅助数组怎 么计算？复杂度是多少？ 我们发现计算next实际上以 为母串、T 实际上以T为母串 实际上以 为母串、 为子串的一个特殊“扩展的KMP”。用上 为子串的一个特殊“扩展的 ” 文介绍的完全相同的算法计算next即可。 （用next本身计算next，具体可以参考标准 KMP）此不赘述。
Thank you！
容易发现，如果有某个位置i满足 extend[i]=m，那么T就肯定在S中出现过， 并且进一步知道出现首位置是i——而这正 是经典的KMP问题。 因此可见“扩展的KMP问题”是对经典 KMP问题的一个扩充和加难。
例子 S=’aaaaaaaaaabaa a’, T=’aaaaaaaaaaa’。
比如ababab ，next[2] = 4， 2，3匹配0，1 ；然后4，5匹配2，3；相当 于还是匹配0，1 ；所以0，1被重复了3次， 所以只要是能匹配上的，就是在重复前i个 字符 ，能匹配多长，就是重复了多长，直 接用i+next[i]就是最长的长度 。
求解extend数组的模板
void GetExtand(const EleType str[], int strLen, int extand[], const EleType mode[], int modeLen, int next[]) { int i, a, p, j(-1); for (i = 0; i < strLen; ++i, --j) { if (j < 0 || i + next[i - a] >= p) { if (j < 0) j = 0, p = i; while (p < strLen && j < modeLen && str[p] == mode[j]) ++p, ++j; extand[i] = j, a = i; } else extand[i] = next[i - a]; } }

KMP算法
有动画，建议下载后观看
第1页，共25页。
有这样一个字符串：
BBC ABCDAB ABCDABCDABDE
我想知道，里面是否包含另一个字符串
ABCDABD
第2页，共25页。
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第 一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
第19页，共25页。
下面介绍《NEXT值表》是如何产生的。
第20页，共25页。
第一位的next值必定为-1； 计算第n个字符的NEXT值：
1.查看第n-1个字符对应NEXT值，设为a；
2.判断a是否为-1，若为-1，则第n个字符next值为0
3.若不为-1，将第n-1个字符与第a个字符比较 4.如果相同，第n个字符对应的NEXT值为a+1 5.如果不同，令a等于第a个字符的NEXT值，执行第第2步。
继续把它向后移，这样就提高了效率。
BBC ABCDAB ABCDABCDABDE
ABCDABD
第11页，共25页。
怎么利用这个已知信息呢？
第12页，共25页。
可以针对搜索词，算出一张《NEXT值表》，即失败指针。
这张表是如何产生的，等下再介绍，这里只要会用就可以了。
第13页，共25页。
已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，字符D 对应的“NEXT值"为2，因此按照下面的公式算出向后移动的位数：
BBC ABCDAB ABCDABCDABDE ABCDABD
第18页，共25页。
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要

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 }。

KMP算法思想80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。

目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。

我们继续往下看：现在讨论一般情况。

假设主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串：p: ‘p(1) p(2) p(3)…..p(m)’把课本上的这一段看完后，继续现在我们假设主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k<j)个字符继续比较此时，s(i)≠p(j), 有主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….|| (相配) || ≠(失配)匹配串： P(1) ……. p(j-1) p(j)由此，我们得到关系式‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：(k<j),‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’即：主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….|| (相配) || || ?(有待比较)匹配串：P(1) p(2) …… p(k-1) p(k)现在我们把前面总结的关系综合一下有：S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……|| (相配) || || || ≠(失配)P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)|| (相配) || || ?(有待比较)P(1) p(2) ……. p(k-1) p(k)由上，我们得到关系：‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’接下来看“反之，若模式串中存在满足式(4-4)。

}
这个版本的求next数组的算法应该是流传最广广泛的，代码是很简洁。可是真的很让人人摸不不到头 脑，它这样计算的依据到底是什什么？ 好，先把这个放一一边，我们自自己己来推导思路路，现在要始终记住一一点，next[j]的值（也就是k）表 示，当P[j] != T[i]时，j指针的下一一步移动位置。 先来看第一一个：当j为0时，如果这时候不不匹配，怎么办？
首首先，对于这个问题有一一个很单纯的想法：从左到右一一个个匹配，如果这个过程中有某个字符不不 匹配，就跳回去，将模式串串向右移动一一位。这有什什么难的？ 我们可以这样初始化：
之后我们只需要比比较i指针指向的字符和j指针指向的字符是否一一致。如果一一致就都向后移动，如 果不不一一致，如下图：
A和E不不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串串的第0位，然后又又重 新开始这个步骤：
}
上面面的程序是没有问题的，但不不够好！如果是人人为来寻找的话，肯定不不会再把i移动回第1位，因 为主串串匹配失败的位置前面面除了了第一一个A之外再也没有A了了，我们为什什么能知道主串串前面面只有一一个 A？因为我们已经知道前面面三个字符都是匹配的！（这很重要）。移动过去肯定也是不不匹配的！ 有一一个想法，i可以不不动，我们只需要移动j即可，如下图：
如图：C和D不不匹配了了，我们要把j移动到哪？显然是第1位。为什什么？因为前面面有一一个A相同啊：
如下图也是一一样的情况：
可以把j指针移动到第2位，因为前面面有两个字⺟母是一一样的：
至至此我们可以大大概看出一一点端倪，当匹配失败时，j要移动的下一一个位置k。存在着这样的性质： 最前面面的k个字符和j之前的最后k个字符是一一样的。 如果用用数学公式来表示是这样的
上面面的这种情况还是比比较理理想的情况，我们最多也就多比比较了了再次。但假如是在主 串串“SSSSSSSSSSSSSA”中查找“SSSSB”，比比较到最后一一个才知道不不匹配，然后i回溯，这个的效 率是显然是最低的。 大大牛牛们是无无法忍受“暴暴力力力破解”这种低效的手手段的，于是他们三个研究出了了KMP算法。其思想就如 同我们上边所看到的一一样：“利利用用已经部分匹配这个有效信息，保持i指针不不回溯，通过修改j指 针，让模式串串尽量量地移动到有效的位置。” 所以，整个KMP的重点就在于当某一一个字符与主串串不不匹配时，我们应该知道j指针要移动到哪？ 接下来我们自自己己来发现j的移动规律律：

KMP字符串模式匹配详解收藏个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next[i]确实有很多版本啊，在另外一些面向对象的算法描述书中也有失效函数f(j)的说法，其实是一个意思，即next[j]=f(j-1)+1，不过还是next[j]这种表示法好理解啊：KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。

简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。

可以证明它的时间复杂度为O(m+n).。

一.简单匹配算法先来看一个简单匹配算法的函数：int Index_BF ( char S [ ], char T [ ], int pos ){/* 若串S 中从第pos(S 的下标0≤pos<StrLength(S))个字符起存在和串T 相同的子串，则称匹配成功，返回第一个这样的子串在串S 中的下标，否则返回-1 */int i = pos, j = 0;while ( S[i+j] != '\0'&& T[j] != '\0')if ( S[i+j] == T[j] )j ++; // 继续比较后一字符else{i ++; j = 0; // 重新开始新的一轮匹配}if ( T[j] == '\0')return i; // 匹配成功返回下标elsereturn -1; // 串S中(第pos个字符起)不存在和串T相同的子串} // Index_BF此算法的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T 相比较。

即从j=0 起比较S[i+j] 与T[j]，若相等，则在主串S 中存在以i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即i 增1，而j 退回至0，重新开始新一轮的匹配。

字符串类——KMP⼦串查找算法1，如何在⽬标字符串 s 中，查找是否存在⼦串 p（本⽂代码已集成到字符串类——字符串类的创建（上）中，这⾥讲述KMP实现原理）？ 1，朴素算法： 2，朴素解法的问题：1，问题：有时候右移⼀位是没有意义的；2，KMP 算法可以右移⼀定的位数，提⾼效率； 3，朴素算法和 KMP 算法对⽐⽰例图：2，伟⼤的发现（KMP）：1，匹配失败时的右移位数与⼦串本⾝相关，与⽬标⽆关；2，移动位数 = 已匹配的字符数 - 对应的部分匹配值；1，“已匹配的字符数”已知，“对应的部分匹配值”未知；（2），部分匹配值就是对应元素和从开始元素开始连续相同的个数；3，任意⼦串都存在⼀个唯⼀的部分匹配值；3，部分匹配表⽰例：4，部分匹配表如何获得？1，前缀集：1，除了最后⼀个字符外，⼀个字符串的全部头部组合；2，后缀集：1，除了第⼀个字符以外，⼀个字符串的全部尾部组合；3，部分匹配值：1，前缀集和后缀集最长共有元素的长度；（2），得到共有长度是为了得到对应各个位置前⾯不相同的元素个数，这样如果前⾯不同元素匹配了，那么就可以直接移动的了；4，ABCDABD 部分匹配表⽰例：5，怎么编程产⽣部分匹配表（Partial Matched Table）（递推完成）？1，实现关键：1，PMT[1] = 0（下标为 0 的元素匹配值为 0）；2，从 2 个字符开始递推（从下标为 1 的字符开始递推）；3，假设 PMT[n] = PMT[n-1] + 1（最长共有元素的长度）（这是⼀个贪⼼假设）；4，当假设不成⽴，PMT[n] 在 PMT[n-1]（这⾥是指的第 PMT[n-1] 个元素）个元素的 ll 值上⽤种⼦作为扩展的基础上继续⽐对；1，当当前前⼦集“前后集最长共有元素数”为 0 时，说明其元素都不相等，可以直接⽐较当前⼦集延长⼀字母序列的⾸尾字母，且此⼦集“前后集最长共有元素数”最⼤为 1；2，将 “前后集最长共有元素数”对应的前后缀最为种⼦扩展；3，假设不成⽴时，把已经匹配的前 PMT[n-1] 个元素的“前后集最长共有元素数”（因为必须在相同的位置上扩展才有意义）作为种⼦来扩展；6，部分匹配表的递推与实现： 1，部分匹配表的递推： 2，在 String 中实现部分匹配表：1/* 建⽴指定字符串的 pmt（部分匹配表）表 */2int* String::make_pmt(const char* p) // O(m)，只有⼀个 for 循环3 {4int len = strlen(p);5int* ret = static_cast<int*>(malloc(sizeof(int) * len));67if ( ret != NULL )8 {9int ll = 0; //定义 ll，前缀和后缀交集的最⼤长度数，largest length;第⼀步10 ret[0] = 0; // 长度为 1 的字符串前后集都为空，对应 ll 为 0；1112for(int i=1; i<len; i++) // 从第⼀个下标，也就是第⼆个字符开始计算，因为第 0 个字符前⾯已经计算过了；第⼆步13 {14/* 算法第四步 */15while( (ll > 0) && (p[ll] != p[i]) ) // 当 ll 值为零时，转到下⾯ if() 函数继续判断，最后赋值与匹配表，所以顺序不要错；16 {17 ll = ret[ll - 1]; // 从之前匹配的部分匹配值表中，继续和最后扩展的那个字符匹配18 }1920/* 算法的第三步，这是成功的情况 */21if( p[ll] == p[i] ) // 根据 ll 来确定扩展的种⼦个数为 ll，⽽数组 ll 处就处对应的扩展元素，然后和最新扩展的元素⽐较；22 {23 ll++; // 若相同（与假设符合）则加⼀24 }2526 ret[i] = ll; // 部分匹配表⾥存储部分匹配值 ll27 }28 }2930return ret;31 }7，部分匹配表的使⽤（KMP 算法）：1，不匹配时，移动位置，之后直接从/字符串的/不匹配前字符/的部分匹配值下标处/开始匹配；8，KMP ⼦串查找算法在 String 中的实现：1/* 在字符串 s 中查找⼦串 p */2int String::kmp(const char* s, const char* p) // O(m) + O(n) ==> O(m+n)，只有⼀个 for 循环3 {4int ret = -1;5int sl = strlen(s);6int pl = strlen(p);7 int* pmt = make_pmt(p);89if( (pmt != NULL) && (0 < pl) && (pl <= sl) ) // 判断查找条件10 {11for(int i=0, j=0; i<sl; i++) // i 的值要⼩于⽬标窜长度才可以查找12 {13while( (j > 0) && (s[i] != p[j]) ) // ⽐对不上的时候，持续⽐对，14 {15 j = pmt[j-1];//移动后应该继续匹配的位置，j =j-(j -LL)=LL = PMT[j-1]16 }1718if( s[i] == p[j] ) // ⽐对字符成功19 {20 j++; // 加然后⽐对下⼀个字符21 }2223if( j == pl ) // 这个时候是查找到了，因为 j 增加到了 pl 的长度；24 {25 ret = i + 1 - pl; // 匹配成功后，i 的值停在最后⼀个匹配成功的字符上，这样就返回匹配成功的位置2627break;28 }29 }30 }3132 free(pmt);3334return ret;35 }9，⼩结：1，部分匹配表是提⾼⼦串查找效率的关键；2，部分匹配值定义为前缀和后缀最长共有元素的长度；3，可以⽤递推的⽅法产⽣部分匹配表；4，KMP 利⽤部分匹配值与⼦串移动位数的关系提⾼查找效率；1，每次匹配失败的时候，⼦串不会简单的右移⼀位，⽽是查询部分匹配表中的值，查到后则右移⼀定位数，使算法效率由平⽅变成线性时间；。

kmp模板题给定⼀个整数数组，最多100w个元素。

再给⼀个特征数组，最多１ｗ个元素。

求特征数组在第⼀个数组中第⼀次出现的位置。

如果没有出现，输出－１．有多组数据。

kmp的模板题。

kmp有两种写法。

第⼀种是求出nxt数组，nxt[i]表⽰当i失配时，则跳到nxt[i]的位置。

注意设置nxt[0]=-1。

第⼆种是求出f数组。

f[i]表⽰字符串S[0..i]的最长前后缀公共⼦串的长度。

此时，注意设置f[0]=0。

⾎的教训：将f[0]设成了-1，结果弄了好久。

其中nxt和f的关系(下标均从0开始) nxt[i]=f[i-1]。

⽐较⽽⾔，第⼀种写法更为简单。

#include<bits/stdc++.h>using namespace std;#define MAXN 1000005int num1[MAXN],num2[MAXN],nxt[MAXN],f[MAXN],n,m,t;void getnxt(){nxt[0]=-1;for(int i=1;i<m;i++){int j;for(j=nxt[i-1];j>=0&&num2[i-1]!=num2[j];j=nxt[j]);nxt[i]=j+1;}}int kmp(){for(int i=0,j=0;i<n;i++,j++){while(j>=0&&num1[i]!=num2[j])j=nxt[j];if(j==m-1)return i-m+2;}return -1;}int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&num1[i]);for(int i=0;i<m;i++)scanf("%d",&num2[i]);getnxt();printf("%d\n",kmp());}return 0;}。

KMP算法解决字符串匹配问题作者：原⽂地址:要解决的问题假设字符串str长度为N，字符串match长度为M，M <= N, 想确定str中是否有某个⼦串是等于match的。

返回和match匹配的字符串的⾸字母在str的位置，如果不匹配，则返回-1OJ可参考：暴⼒⽅法从str串中每个位置开始匹配match串，时间复杂度O(M*N)KMP算法KMP算法可以⽤O(N)时间复杂度解决上述问题。

流程我们规定数组中每个位置的⼀个指标，这个指标定义为这个位置之前的字符前缀和后缀的匹配长度，不要取得整体。

例如: ababk 这个字符串，k之前位置的字符串为abab，前缀ab 等于后缀ab，长度为2，所以k位置的指标为2，下标为3的b之前的字符串aba ,前缀a 等于后缀a, 长度为1，所以下标为3的b的指标为1，⼈为规定：下标为0的字符的指标是-1，下标为1的字符的指标0假设match串中每个位置我们都已经求得了这个指标值，放在了⼀个next数组中，这个next数组有助于我们加速整个匹配过程。

假设在某个时刻，匹配的到的字符如下其中str的i..j⼀直可以匹配上match串的0...m, str中的x位置和match串中的y位置第⼀次匹配不上。

如果使⽤暴⼒⽅法，此时我们需要从str的i+1位置重新开始匹配match串的0位置，这样算法的复杂度⽐较⾼。

⽽使⽤KMP算法，利⽤next数组，可以加速这⼀匹配过程，具体流程是，我们可以先得到y位置的next数组信息，假设y的next数组信息是2，如下图那么0...k 这⼀段完全等于f...m这⼀段，所以对于match来说，当y位置匹配不上x位置以后, ⽆需从i+1开始匹配0位置的值，⽽是可以直接让x位置匹配位置p上的值，如下图其中p的位置由y位置的next数组确定，因为y的next数组值为2（即p位置）。

如果匹配上了，则x来到下⼀个位置（即x+1位置），p来到下⼀个位置（即f位置）继续匹配，如果再次匹配不上，假设p位置的next数组值为0, 则继续⽤x匹配0位置上的值，如下图如果x位置的值依旧不等于0位置的值，则宣告本次匹配失败，str串来到x下⼀个位置，match串从0位置开始继续匹配。