【hash】Power Strings

【题意】：

给出s串出来，能否找到一个前缀，通过多次前缀进行拼接。构成s串。如果有多个，请输出最多次数那个。

如：aaaa

可以用1个a，进行4次拼接

可以用2个a，进行2次拼接

可以用4个a，进行1次拼接

提供两种做法：

第一种是：利用kmp算法中求解 longest prefix table的方法，

找到最后一个位置的上的 p[len-1]，如果用总长度减去（len-p[len-1]）能否通过这一个前缀来拼接出来。

就是判断是否能整除。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e6 + 10 ;
 4 char str[N];
 5 int p[N],len;
 6 void get_next(char s[]){
 7     len = strlen( s );
 8     int i = 1 , j = 0 ;
 9     p[0] = 0 ;
10     while( i < len ){
11         if( s[i] == s[j] ){
12             p[i++] = ++j ;
13         }else{
14             if( j > 0 ){
15                 j = p[j-1] ;
16             }else{
17                 p[i] = j ;
18                 i++ ;
19             }
20         }
21     }
22 }
23 int main()
24 {
25     while( cin >> str ){
26         if( str[0] == '.' ) break;
27         get_next( str );
28         int len = strlen( str );
29         printf("%d
",len % (len-p[len-1]) == 0 ?
30             len / (len-p[len-1]) : 1 );
31     }
32     return 0;
33 }

View Code

另一种方法就是：

用双hash来实现，双hash处理前缀和，最后用for循环，枚举所有的因数进行处理。

 1 #include<bits/stdc++.h>
 2 #define Mp make_pair
 3 #define F first
 4 #define S second
 5 using namespace std;
 6 const int N = 1e6+7;
 7 const int M1 = 1e9+7 , M2 = 1e9+9;
 8 typedef long long ll;
 9 typedef struct Node{
10     long long first ,second;
11     Node (){}
12     Node ( ll u,ll v){ first = u , second = v ;}
13 }PII;
14 //typedef pair<ll,ll> PII;
15 
16 const PII base{M2,M1},p{M1,M2},One{1ll,1ll},Zero{0ll,0ll};
17 
18 PII operator - (PII u,PII v){
19     return Node( (u.first-v.first+p.first)%p.first ,(u.second-v.second+p.second)%p.second );
20 }
21 PII operator * ( PII u , PII v ){
22     return Node( (u.first*v.first)%p.first , (u.second*v.second)%p.second );
23 }
24 PII operator + ( PII u , PII v ){
25     return Node( (u.first+v.first)%p.first , (u.second+v.second)%p.second );
26 }
27 PII operator + ( PII u , int v ){
28     return Node( (u.first+v)%p.first , (u.second+v)%p.second );
29 }
30 bool operator != ( PII u,PII v ){
31     return !( u.first == v.first && u.second == v.second );
32 }
33 PII Pow( PII a ,int b){
34     PII ans = One ;
35     while( b ){
36         if( b&1 )
37             ans = ans * a ;
38         b >>= 1 ;
39         a = a * a ;
40     }
41     return ans ;
42 }
43 PII sum[N];
44 char str[N];
45 int main()
46 {
47     ios_base :: sync_with_stdio(0);
48     cin.tie(NULL),cout.tie(NULL);
49 
50     while( cin >> str+1 ){
51         if( str[1] == '.') break;
52         int len = strlen(str+1);
53 
54         sum[0] = Zero ;
55         for(int i=1;i<=len;i++)
56             sum[i] = sum[i-1] * base + str[i];
57         int ans = 1 ;
58         for(int i=1;i<=len/2;i++){
59             if( len % i ) continue ;
60             bool flag = false ;
61             for(int j=i ; !flag && j<=len; j+=i ){
62                 if( sum[j] - sum[j-i] * Pow(base,i) != sum[i] ){
63                     flag = true ;
64                 }
65             }
66             if( !flag ) {
67                 ans = len/i ;
68                 break;
69             }
70         }
71         cout << ans << endl ;
72     }
73     return 0;
74 }

BKDR