首页 > 代码库 > NOIP2017SummerTraining0705 T1 重复字符串

NOIP2017SummerTraining0705 T1 重复字符串

题目描述

给定两个字符串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

提示

 

30%的数据:字符串的长度≤1000;


100%的数据:字符串的长度≤1000000, m≤10,字符串内只含小写字母。

 

看到这道题目后,我们先不要来想正解,我们来想暴力吧

暴力其实非常水啊

枚举一个字符串,再枚举这个长度,最后在比较一下是否全部符合就可以拿到30分啦啦啦,美滋滋

然后在比较字符串的时候有没有觉得一个一个去比(字符串比较是逐位比较的)实在是太浪费了、

于是我们异想天开地想用数字去代替字符

好消息是这种方法是存在的哦

那就是Hash大法

我们可以使用Hash将字符串转为数字,这样比较就由O(N) 下滑为 O(1)啦,美滋滋

技术分享
 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 long long Mod1=1920454134;
10 long long A[1000005];
11 char s1[1000005];
12 
13 int main()
14 {
15     int _;
16     scanf("%d",&_);
17     while (_--)
18     {
19         scanf("%s",s1);
20         int Len=strlen(s1);
21         long long K=1;
22         for (int i=1; i<=Len; i++)
23         {
24             A[i]=((A[i-1] % Mod1) + (long long)(s1[i-1] - 97) * K % Mod1) % Mod1;
25             K=K * 26 % Mod1;
26         }
27         K=1;
28         for (int i=1; i<=Len; i++)
29         {
30             K=K * 26 % Mod1;
31             if (Len % i == 0)
32             {
33                 long long Tmp=A[i];
34                 long long Sum=Tmp;
35                 bool flag1=false;
36                 for (int j=2; i*j <= Len; j++)
37                 {
38                     Sum=(Sum * K % Mod1 + Tmp) % Mod1;
39                     if (Sum != A[i * j])
40                     {
41                         flag1=true;
42                         break;
43                     }
44                 }
45                 if (! flag1)
46                 {
47                     printf("%d\n",Len / i);
48                     break;
49                 }
50             }
51         }
52     }
53 }
Show My Ugly Code

 

NOIP2017SummerTraining0705 T1 重复字符串