/*该段话为转载,很精确.
大致题意:
给出一个字符串,求出这个字符串最多能够由多少个子串首尾连接而成。比如“ababab”就是由3个“ab”相连而成,所以输出3,“abcdef”只能看作一个“abcdef”所以输出1。
大致思路:
KMP中next数组的巧妙运用。在这里我们假设这个字符串的长度是len,那么如果len可以被len-next[len]整除的话,我们就可以说len-next[len]就是那个最短子串的长度
为什么呢? 假设我们有一个字符串ababab,那么next[6]=4对吧,由于next的性质是,匹配失败后,下一个能继续进行匹配的位置,也就是说,把字符串的前四个字母,abab,平移2个单位,这个abab一定与原串的abab重合(否则就不满足失败函数的性质),这说明了什么呢,由于字符串进行了整体平移,而平移后又要重叠,那么必有
s[1]=s[3],s[2]=s[4],s[3]=s[5],s[4]=s[6].说明长度为2的字符串在原串中一定重复出现,这就是len-next[len]的含义!*/
#include <cstring>
#include <stdio.h>
const int maxn=1000005;
int next[maxn];
void ready(char *mode,int lenb)
{
next[0]=-1;
int j=-1;
for(int i=1; i<lenb; i++)
{
while(j>-1&&mode[j+1]!=mode[i]) j=next[j];
if(mode[j+1]==mode[i]) j++;
next[i]=j;
}
}
int main()
{
char mode[maxn];
while(scanf("%s",mode)!=EOF&&strcmp(mode,".")!=0)
{
int len=strlen(mode);
ready(mode,len);
int m=len-1-next[len-1];
if(len%m==0) printf("%d\n",len/m);
else printf("1\n");
}
return 0;
}
分享到:
相关推荐
pku acm 2406 Power Strings代码 kmp算法。解题报告:http://blog.csdn.net/china8848
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
KMP算法
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
数据结构中KMP算法过程的Flash演示
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
简单的kmp算法实现,代码结构十分清晰,适合初学者理解kmp算法
基于KMP算法的字符串匹配源码, 支持通配符,单匹配和多重匹配。 效率比较高
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
使用并行计算编程工具OpenMp实现kmp串匹配
kmp算法:查找一个字符串是不是另一个字符串的子串
易语言KMP算法模块源码,KMP算法模块,kmp_init,kmp_find,字节集_子字节集寻找
KMP、Mancher和扩展KMP算法详解,但是其中的参考代码有一点小错误,请自行参考网络