【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]）能否通过这一个前缀来拼接出来。

就是判断是否能整除。

 #include<bits/stdc++.h>

 using namespace std;

 const int N = 1e6 +  ;

 char str[N];

 int p[N],len;

 void get_next(char s[]){

     len = strlen( s );

     int i =  , j =  ;

     p[] =  ;

     while( i < len ){

         if( s[i] == s[j] ){

             p[i++] = ++j ;

         }else{

             if( j >  ){

                 j = p[j-] ;

             }else{

                 p[i] = j ;

                 i++ ;

             }

         }

     }

 }

 int main()

 {

     while( cin >> str ){

         if( str[] == '.' ) break;

         get_next( str );

         int len = strlen( str );

         printf("%d\n",len % (len-p[len-]) ==  ?

             len / (len-p[len-]) :  );

     }

     return ;

 }

另一种方法就是：

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

 #include<bits/stdc++.h>

 #define Mp make_pair

 #define F first

 #define S second

 using namespace std;

 const int N = 1e6+;

 const int M1 = 1e9+ , M2 = 1e9+;

 typedef long long ll;

 typedef struct Node{

     long long first ,second;

     Node (){}

     Node ( ll u,ll v){ first = u , second = v ;}

 }PII;

 //typedef pair<ll,ll> PII;

 const PII base{M2,M1},p{M1,M2},One{1ll,1ll},Zero{0ll,0ll};

 PII operator - (PII u,PII v){

     return Node( (u.first-v.first+p.first)%p.first ,(u.second-v.second+p.second)%p.second );

 }

 PII operator * ( PII u , PII v ){

     return Node( (u.first*v.first)%p.first , (u.second*v.second)%p.second );

 }

 PII operator + ( PII u , PII v ){

     return Node( (u.first+v.first)%p.first , (u.second+v.second)%p.second );

 }

 PII operator + ( PII u , int v ){

     return Node( (u.first+v)%p.first , (u.second+v)%p.second );

 }

 bool operator != ( PII u,PII v ){

     return !( u.first == v.first && u.second == v.second );

 }

 PII Pow( PII a ,int b){

     PII ans = One ;

     while( b ){

         if( b& )

             ans = ans * a ;

         b >>=  ;

         a = a * a ;

     }

     return ans ;

 }

 PII sum[N];

 char str[N];

 int main()

 {

     ios_base :: sync_with_stdio();

     cin.tie(NULL),cout.tie(NULL);

     while( cin >> str+ ){

         if( str[] == '.') break;

         int len = strlen(str+);

         sum[] = Zero ;

         for(int i=;i<=len;i++)

             sum[i] = sum[i-] * base + str[i];

         int ans =  ;

         for(int i=;i<=len/;i++){

             if( len % i ) continue ;

             bool flag = false ;

             for(int j=i ; !flag && j<=len; j+=i ){

                 if( sum[j] - sum[j-i] * Pow(base,i) != sum[i] ){

                     flag = true ;

                 }

             }

             if( !flag ) {

                 ans = len/i ;

                 break;

             }

         }

         cout << ans << endl ;

     }

     return ;

 }

BKDR

巴特西

【hash】Power Strings

最新文章

热门文章