P4391时间复杂度计算

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e7+7, base = 31, N = 1e7+10;
int d,p[N],hsh[N];//p[i] = base^i, hsh[i] = 前i个字符组成字符串的哈希值(记得mod)
string s;

bool check(int len){
    int tip = hsh[len], yu = d%len, i;
    for (i = len*2; i <= d - yu; i += len) //滚动哈希看是否重复
		if(tip != (hsh[i] - 1LL * hsh[i-len] * p[len] % MOD + MOD) % MOD) return false;
    if(yu != 0) //看尾部余出来的部分
		if(hsh[yu] != (hsh[d] - 1LL * hsh[d-yu] * p[yu] % MOD + MOD) % MOD) return false;
    return true;
}

int main(){
    cin>>d;
    cin>>s; 
    //初始化
    p[0] = 1;
    for (int i = 1; i <= d; i++)
    {
        p[i] = 1ll * p[i-1] * base % MOD;
        hsh[i] = (1ll * hsh[i-1] * base % MOD + s[i-1] - 'a' + 1) % MOD; 
    }
    for (int i = 1; i <= d; i++)//枚举重复的字符串长度
        if(check(i)){
            cout<<i<<endl;
            return 0;
        }
    return 0;
}