Passwords
Time Limit: 3000ms
Memory Limit: 131072KB
This problem will be judged on UVALive. Original ID: 650764-bit integer IO format: %lld Java class name: Main
解题：好高深的hash啊
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn = 205; 5 const int base = 233; 6 const int mod = 1e9+7; 7 char str[maxn][20010]; 8 LL hs[maxn][20010],B[20010]; 9 int n; 10 unordered_map<LL,int>ump; 11 void init(){ 12 B[0] = 1; 13 for(int i = 1; i < 20010; ++i) 14 B[i] = B[i-1]*base%mod; 15 } 16 LL calc(int i,int L,int R){ 17 return ((hs[i][R] - hs[i][L-1]*B[R - L + 1])%mod + mod)%mod; 18 } 19 void solve(){ 20 ump.clear(); 21 for(int i = 0; i < n; ++i){ 22 for(int j = 1,len = strlen(str[i] + 1); j <= len; ++j){ 23 hs[i][j] = (hs[i][j-1]*base + str[i][j])%mod; 24 ump[hs[i][j]]++; 25 } 26 } 27 int a = 0,b = 0; 28 for(int i = 0; i < n; ++i){ 29 int len = strlen(str[i] + 1); 30 for(int j = 1; j <= len; ++j) --ump[hs[i][j]]; 31 for(int j = 1; j <= len; ++j){ 32 LL suffix = calc(i,len - j + 1,len); 33 if(!ump[suffix]) continue; 34 int x = 1,y = 1; 35 LL prefix = suffix; 36 for(int k = 2; k*j <= len; ++k){ 37 LL suffix2 = calc(i,len - j*k + 1,len); 38 prefix = (prefix*B[j] + suffix)%mod; 39 if(suffix2 != prefix) break; 40 if(ump[prefix]) x = k; 41 y = k; 42 } 43 if(x == y && x == 1) continue; 44 if(x == y) --x; 45 if(j*(x + y) > a + b){ 46 a = x*j; 47 b = y*j; 48 } 49 } 50 for(int j = 1; j <= len; ++j) ump[hs[i][j]]++; 51 } 52 printf("%d %d ",a,b); 53 } 54 int main(){ 55 int kase; 56 init(); 57 scanf("%d",&kase); 58 while(kase--){ 59 scanf("%d",&n); 60 for(int i = 0; i < n; ++i) 61 scanf("%s",str[i] + 1); 62 solve(); 63 } 64 return 0; 65 } 66 /* 67 2 68 3 69 abcabe 70 defg 71 bcabab 72 */