1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <vector>#include <list>#include <map>#include <set>#include <deque>#include <queue>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <cctype>#include <string>#include <cstring>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>using namespace std;typedef long long LL;#define CLR(x,y) memset((x),(y),sizeof((x)))#define getint(x) scanf("%d",&(x))#define get2int(x,y) scanf("%d%d",&(x),&(y))#define get3int(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))#define getll(x) scanf("%I64d",&(x))#define get2ll(x,y) scanf("%I64d%I64d",&(x),&(y))#define get3ll(x,y,z) scanf("%I64d%I64d%I64d",&(x),&(y),&(z))#define getdb(x) scanf("%f",&(x))#define get2db(x,y) scanf("%f%f",&(x),&(y))#define get3db(x,y,z) scanf("%f%f%f",&(x),&(y),&(z))#define getstr(str) scanf("%s",str)#define rep(x,y,z) for((x)=(y);(x)<(z);(x)++)#define repd(x,y,z) for((x)=(y);(x)>=(z);(x)--)const int maxm = 100000 + 10;int nextt[maxm];void makenext(char p[],int m){ CLR(nextt,0); for(int i= 1,j = 0;i < m ;) { if(p[i] == p[j]) nextt[i++] = ++j; else if (j > 0) j = nextt[j-1]; else i++; }}int main(){ int t;getint(t); char str[maxm]; while(t--) { getstr(str); int len = strlen(str); makenext(str,len); int tmp = len - nextt[len - 1]; int res; if(len % tmp || tmp == len) res = tmp - len % tmp; else res = 0; printf("%d\n",res); } return 0;} |
[2016-02-04][HDU][3746][Cyclic Nacklace]
原文：http://www.cnblogs.com/qhy285571052/p/5180837.html