想用最小循环子串做,但是只有25分

P3435 [POI2006] OKR-Periods of Words

IQAQI @ 2024-04-30 11:20:10

是我想的太简单了吗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;
}

by mayike @ 2024-05-01 11:46:22

@IQAQI

若是这个串 aabcaa,你这种做法会求出 aabc 为周期,而最大周期应为 aabca


by IQAQI @ 2024-05-02 15:59:33

@mayike 明白了谢谢佬orz


|