UVa 455 Periodic Strings

题目描述题目要求找出一个字符串的最小周期kkk。周期定义为字符串可以由某个长度为kkk的子串重复多次拼接而成。例如字符串abcabcabcabc的周期可以是333、666或121212最小周期为333。输入格式第一行一个整数NNN表示测试用例的数量后面跟一个空行。每个测试用例一行包含一个由非空白字符组成的字符串长度不超过808080。两个连续测试用例之间由一个空行分隔。输出格式对于每个测试用例输出一行一个整数表示该字符串的最小周期。两个连续测试用例的输出之间由一个空行分隔。样例输入1 HoHoHo输出2题目分析本题的核心是寻找字符串的最小周期。周期kkk必须满足kkk能整除字符串长度LLL且字符串可以被前kkk个字符重复L/kL/kL/k次得到。枚举法由于字符串长度L≤80L \le 80L≤80可以直接枚举可能的周期kkk从111到LLL若L mod k≠0L \bmod k \ne 0Lmodk0则kkk不可能是周期。否则检查字符串是否由前kkk个字符重复构成取前kkk个字符作为模式。从第kkk个字符开始每kkk个字符一组与模式比较若全部相同则kkk为周期。找到的第一个满足条件的kkk即为最小周期。优化可以在字符串中寻找第一个与首字符相同的位置作为候选周期但直接枚举kkk足够高效。复杂度分析枚举O(L)O(L)O(L)种周期每次检查O(L)O(L)O(L)个字符总复杂度O(L2)O(L^2)O(L2)L≤80L \le 80L≤80完全可接受。代码实现// Periodic Strings// UVa ID: 455// Verdict: Accepted// Submission Date: 2016-07-15// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn;cinn;string line;for(inti1;in;i){if(i1)coutendl;cinline;boolperiod_existfalse;size_t nextline.find(line.front(),1);while(next!line.npos){if(line.length()%next0){boolis_sametrue;size_t beginnext;while(beginline.length()){for(size_t i0;inext;i)if(line[i]!line[ibegin]){is_samefalse;break;}beginnext;}if(is_same){coutnextendl;period_existtrue;break;}}nextline.find(line.front(),next1);}if(!period_exist)coutline.length()endl;}return0;}