【题意】：
给出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