【KMP】重复子串-白红宇

【KMP】重复子串

阅读量：697 次

发布时间：2019-03-14

本文共 862 字，大约阅读时间需要 2 分钟。

小目录

链接

题目描述

给定若干个的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。

样例输入

abcdaaaaababab.

样例输出

思路

对于每一个字符串，我们可以用 $k m p$ 算法，求出 $p$ 值，则s串的第一位到第 $p_n$ 位和 $n - p_n$ 到第 $n$ 位都是匹配的，那如果 $n\ \% (n - p_n) == 0$ ，那就代表着存在重复子串，长度就为 $n - p_n$ ，个数为 $\frac{n}{n - p_n}$

代码

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;char s[10000005];int len, p[10000005];int main(){   	scanf("%s", s + 1);	len = strlen(s + 1);	while(len != 1 || s[1] != '.')	{   		len = strlen(s + 1);		int j = 0;		for(int i = 2; i <= len; ++i)		{   			while(j && s[i] != s[j + 1]) j = p[j];			if(s[i] == s[j + 1]) ++j;			p[i] = j;		}//KMP算法		if(len % (len - p[len]) == 0) printf("%d\n", len / (len - p[len]));//判断		else printf("1\n"); 		scanf("%s", s + 1);		len = strlen(s + 1);	}	return 0;}

转载地址：http://bbzlz.baihongyu.com/

你可能感兴趣的文章