首页 > 代码库 > 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 }
NOIP2017SummerTraining0705 T1 重复字符串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。