题目描述
给你一个字符串s1,它是由某个字符串s2,s2不断自我连接形成的。但是字符串 s2是不确定的,现在只想知道它的最短长度是多少。
输入格式
第一行一个整数 LL,表示给出字符串的长度。
第二行给出字符串s1的一个子串,全由小写字母组成。
进制哈希法
1、求出前缀的哈希值
2、子串的哈希值 = h[R] - h[L-1] * P [ R - L + 1]
3、只需比较哈希值是否相等就能判断是不是同一个子串
用途:最长回文,子串比较
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 50010;
int PP = 131;
ull h[N] , P[N] , n;
char s[N];
ull get_hash(int L, int R){
return (h[R] - h[L-1]*P[R-L+1]);
}
int main(){
cin >> n;
scanf("%s",s+1);
for(int i = 1; i <= n ; i ++){
h[i] = h[i-1] * PP + s[i];
}
P[0] = 1;
for(int i = 1 ; i <= N - 1 ; i ++){
P[i] = P[i-1] * PP;
}
for(int i = 1 ; i <= n ; i ++){
ull flag = 1;
ull last =get_hash(1,i);
for(int j = 1 ; (j + 1) * i <= n ; j ++){
if(get_hash(j * i + 1, (j + 1)* i) != last){
flag = 0;
break;
}
}
if(n * 1 != 0){
ull len = n % i;
if(get_hash(1,len) != get_hash(n-len+1,n)) flag = 0;
}
if(flag) {
printf("%d\n",((int)i));
break;
}
}
}