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