关键词：
KMP算法用来解决一系列字符串单模式匹配问题，其以难理解，难记忆著称。其next数组的构造就如同AC自动机中的fail指针，就是如果匹配失败，字符串应从哪里开始继续匹配。这里的next数组表示：next[i]=前i个字符的公共最长前后缀长度。觉得对于KMP算法，这篇写的不错——http://www.cnblogs.com/c-cloud/p/3224788.html。
现在来讲一下应用。
给定两个字符串a和b，我们可以定义一些操作：a*b为将字符串a和字符串b连接起来，比如a= "aoe"，b= "jkw"，那么a*b= "aoejkw"。进一步，我们可以有指数操作，a^0= ""， a^1=a， a^2=a*a， a^n=a*(a^(n-1))=a*a*…*a (n个a)
现在给你一个字符串，你可以将它看成是a^n的形式，比如字符串"abababab"，可以认为是"abab"^2， 也可以是"abababab"^1，还可以是"ab"^4。
现在问题是，给定的字符串，我们想让它变成a^n中的n达到最大，那么这个n最大是多少？例如："abababab"最大的n是4。
输入
第一行，一个整数m，表示有m个字符串。
接下来m行每行输入一个只含小写字母的字符串。
输出
输出m行，对于每行输出相应字符串的最大n。
样例输入
3 abcde aaaaaa abababab
样例输出
1 6 4
提示
这道题一看觉得不是特别会，暴力算法老王的bloghttp://www.cnblogs.com/TUncleWangT/p/7162665.html讲了，正解就是运用了KMP算法里的next数组。我们令原字符串长度为S，重复字符串长度为T，则S=K*T,由定义可知next[S]=(K-1)*T;所以S-next[S]=T,判断一下整除就好了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; char str[1000005]; int next[1000005]; void make_next() { int len=strlen(str),q,k; next[0]=0; for(q=1,k=0;q<len;q++) { while(k>0&&str[q]!=str[k]) { k=next[k-1]; } if(str[k]==str[q]) k++; next[q]=k; } } void Debug() { int len=strlen(str); for(int i=0;i<len;i++) cout<<next[i]<<' '; } void work() { int tmp=strlen(str)-next[strlen(str)-1]; if(strlen(str)%tmp==0) cout<<(strlen(str)/tmp)<<endl;else cout<<1<<endl; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",str); make_next(); work(); } }
kmp算法模板及理解
kmp算法是复杂度为O(n+m)的字符串匹配算法;首先kmp算法的核心是在模式串中获得next数组,这个数组表示模式串的子串的前缀和后缀相同的最长长度;这样在匹配的过程中如果指到不匹配的位置,模式串用next数组进行跳转到符合的位置... 查看详情
kmp算法及python代码
KMP算法python代码1:#-*-coding:utf-8-*-defkmp_in(str_a,str_b):"""判断a字符串是否包含b字符串的kmp算法"""#先算出部分匹配表len_a=len(str_a)len_b=len(str_b)cha=len_b-len_aprint'cha:%s'%cha 查看详情
字符串匹配（kmp）算法及java实现
一、什么是KMP算法？ 维基百科的解释是：在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息... 查看详情
kmp算法证明及实现
KMP算法一、普通的字符串匹配 平时我们在写普通的字符串匹配算法的时候，是拿着要匹配的串去匹配被匹配的串，字符逐个比较，当发现字符失配时，被匹配的字符串的指针要回到前一次开始匹配的指... 查看详情
kmp模板及总结
KMP是一种字符串匹配算法，它在时间复杂度上较暴力匹配算法由很大的优势。比如我要找字符串S中是否存在子串P，如果暴力匹配的话，则时间复杂度为O（n*m），而kmp算法时间复杂度为O（n+m）。这里我们有一个辅助的数组next[]... 查看详情
数据结构串---kmp模式匹配算法实现及优化(代码片段)
KMP算法实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineMAXSIZE40typedefintElemType;typedefin 查看详情
kmp算法原理与应用（简单易懂)
kmp算法的正确性证明及一个小优化
...有点不太公道呀。。。无所谓啦反正各位看着开心就行KMP算法对于模式串$P$，建立其前缀函数$N$，其中$N[q]$表示在$P$中，以$q$位置为结束的可以匹配到前缀的最长后缀的长度（也可以理解为那个前缀的结束位置），在匹配中，若... 查看详情
kmp算法的应用
Giventwosequencesofnumbers:a[1],a[2],......,a[N],andb[1],b[2],......,b[M](1<=M<=10000,1<=N<=1000000).YourtaskistofindanumberKwhichmakea[K]=b[1],a[K+1]=b[2],......,a[K+M-1]=b[M].Iftherearem 查看详情
kmp算法应用举例(代码片段)
KMP是字符串匹配的经典算法也是众多字符串基础的重中之重A.题意：给T组数据，每组有长度为n和m的母串和模式串。判断模式串是否是母串的子串，如果是输出最先匹配完成的位置，否则输出-1.做法：直接套用模板。把char改成int... 查看详情
kmp算法及python代码
KMP算法python代码1:#-*-coding:utf-8-*-defkmp_in(str_a,str_b):"""判断a字符串是否包含b字符串的kmp算法"""#先算出部分匹配表len_a=len(str_a)len_b=len(str_b)cha=len_b-len_aprint'cha:%s'%chapart_match=[]forxinrange(1,len_a+1):st... 查看详情
kmp算法(代码片段)
目录KMP算法基本思想计算next数组前缀和后缀公共部分的最大长度next数组匹配字符串KMP算法基本思想算法由两部分组成计算ptr每一位及之前的字符串中，前缀和后缀公共部分的最大长度的next数组匹配ptr和str，当ptr失配时，利用nex... 查看详情
数据结构kmp算法配图详解（超详细）(代码片段)
文章目录一、什么是KMP算法？二、KMP算法的解决题型三、模式串移动距离的判断（next数组）四、KMP算法的具体实现五、KMP算法的时间复杂度六、next数组的改进--nextval数组及具体代码七、最后的话一、什么是KMP算法... 查看详情
第四十二课kmp算法的应用(代码片段)
思考： replace图解： 程序完善： DTString.h：1#ifndefDTSTRING_H2#defineDTSTRING_H34#include"Object.h"56namespaceDTLib789classString:Object1011protected:12char*m_str;13intm_ 查看详情
kmp算法深度解析
摘要：KMP算法是字符串匹配的经典算法，由于其O(m+n)的时间复杂度，至今仍被广泛应用。大道至简，KMP算法非常简洁，然而，其内部却蕴含着玄妙的理论，以至许多人知其然而不知其所以然。本文... 查看详情
字符串-kmp算法(代码片段)
字符串算法中，字符串匹配是一个非常重要的应用。例如在网页中查找关键词，其实就是在对字符串匹配，也就是看一个主字符串中是否包含了一个子字符串。而KMP算法在字符串匹配方法中一个很著名并且很聪明的算法，当然也... 查看详情
kmp算法讲解(代码片段)
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹... 查看详情
kmp算法(代码片段)
KMP算法1.算法介绍KMP是一个解决模式串在文本串是否出现过，若出现过，最早出现的位置的算法Knuth-Morris-Pratt字符串查找算法，简称“KMP算法”，此算法由DonaldKnuth、VaughanPratt、JamesH.Morris三人于1977年联合发表，故使用三人姓氏命... 查看详情