JZOJ 5272 神奇的重复序列

其实是个挺正经的算法，但是我实在不知道加什么标签了（

首先考虑一下两个子串相同意味着什么。
设这两个子串为 Sl1…r1,Sl2…r2 (r1−l1=r2−l2)，那么对于任意 i,j∈[l1,r1]∪[l2,r2],i≡j(mod|l1−l2|) 有 Si=Sj。

于是考虑枚举 d=|l1−l2| 并枚举其中一个右端点，按照下标模 d 的值分类，维护每一类下标中字符的众数，即可得出将两个子串改成完全相同至少需要改动多少个字符。
结合双指针维护左端点即可。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e3;
int n,k,head;
char s[N + 5];
int cnt[N + 5][26];
int sum[N + 5],mx[N + 5];
int c,ans;
inline void insert(int d,int i,int x,int k)
{
    cnt[i][x] += k;
    c -= sum[i] - mx[i];
    sum[i] += k;
    if(k > 0)
        mx[i] = max(mx[i],cnt[i][x]);
    else
    {
        mx[i] = 0;
        for(register int j = 0;j < 26;++j)
            mx[i] = max(mx[i],cnt[i][j]);
    }
    c += sum[i] - mx[i];
}
int main()
{
    freopen("repeat.in","r",stdin),freopen("repeat.out","w",stdout);
    scanf("%d%s",&k,s + 1),n = strlen(s + 1);
    for(register int d = 1;d < n;++d)
    {
        c = 0;
        for(register int i = head = 1 + d;i <= n;++i)
        {
            insert(d,i % d,s[i] - 'a',1),i - d < head && (insert(d,i % d,s[i - d] - 'a',1),1);
            for(;head <= i && c > k;insert(d,head % d,s[head - d] - 'a',-1),head > i - d && (insert(d,head % d,s[head] - 'a',-1),1),++head);
            ans = max(ans,i - head + 1);
            if(i == n)
                for(register int j = head;j <= n;++j)
                    --cnt[j % d][s[j] - 'a'],sum[j % d] = mx[j % d] = 0,
                    j - d < head && (--cnt[(j - d) % d][s[j - d] - 'a'],sum[(j - d) % d] = mx[(j - d) % d] = 0);
        }
    }
    printf("%d\n",ans);
}