WZOI-354找子串

题目描述:

给定两个字符串a和b，我们定义a*b表示字符串的连接。例如，如果a=”abc”,b=”def”，那么a*b=“abcdef”，如果这种连接是多重的，可以用幂的形式来定义：a^0=“” (空串)，a^（n+1）=a*(a^n)。

输入格式:

只有一行表示一个字符串s，长度至少为1，不超过100

输出格式:

输出最大的n值，如s=a^n(a是某个字符串)

样例输入:

样例1：
abcd

样例2：
aaaa

样例3：
ababab

样例输出:

样例1：
1

样例2：
4

样例3：
3

提示:

本题要用到C++字符串的一些命令。

1）定义字符串类型

    string  s;      //长度无限长

2）读入一行字符串

    cin >> s;   //读到空格为止

    getline ( cin ,  s )   //以行为单位，读入整行内容给 s

3）求字符串的长度：

     s.length( )

4）查看字符串的某一位置的字符：

      s [ i ]

5）取字符串当中的某一段子串：

     s.substr( i , 3 )   //在s字符串从i位开始连续取长度为3的子串。

6）字符串的比较：

     两串字符串s1和s2，可以直接用>、<、＝＝等关系运算符进行比较。

时间限制: 1000ms
空间限制: 256MB

代码如下：
 

#include<bits/stdc++.h>
using namespace std;
int a[1000005],len;
char s[1000010];
void fun(){
    int i=0;
	int j=-1;
	a[0]=-1;
	while(i<len){
	   if(j==-1||s[i]==s[j]){
	      i++;
		  j++;
		  a[i]=j;
	   }else{
	   		j=a[j];
	   }   
	}
}
int main(){
	while(scanf("%s",s)!=EOF){
		if(s[0]=='.'){
			break;
		}
	   len=strlen(s);
       fun();
	   if(len%(len-a[len])==0){
	      printf("%d\n",len/(len-a[len]));
	   }else{
	      printf("1\n");
	   }
	}
	return 0;
}