想用最小循环子串做,但是只有25分
查看原帖
想用最小循环子串做,但是只有25分
1078604
IQAQI楼主2024/4/30 11:20

是我想的太简单了吗QAQ

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000001;
long long kmp[maxn];
char s[maxn];
long long l, j;
int main()
{
    cin >>l>> s + 1;
    for (int i = 2; i <= l; ++i) {
        while (j && s[j + 1] != s[i])j = kmp[j];
        if (s[j + 1] == s[i])kmp[i] = ++j;
    }//利用next数组求最小循环子串
    long long ans = 0;
    for (long long i = 2; i <= l; ++i) {
        long long min_circle = i - kmp[i];
        //cout << "前" << i << "个字符最小循环为" << min_circle << endl;
        if (min_circle > 0) {
            if (i % min_circle == 0)ans += i - min_circle;//如果最小循环子串可以组成前i个字符
            else ans += i - (i % min_circle);//如果不能组成前i个字符,答案就减掉多余的部分
        }
    }
    cout << ans;
}
2024/4/30 11:20
加载中...