其实是个挺正经的算法，但是我实在不知道加什么标签了（
首先考虑一下两个子串相同意味着什么。
设这两个子串为 \(S_{l_1\dots r_1},S_{l_2\dots r_2}\ (r_1 - l_1 = r_2 - l_2)\)，那么对于任意 \(i,j \in [l_1,r_1] \cup [l_2,r_2],i \equiv j \pmod{|l_1-l_2|}\) 有 \(S_i = S_j\)。
于是考虑枚举 \(d = |l_1 - l_2|\) 并枚举其中一个右端点，按照下标模 \(d\) 的值分类，维护每一类下标中字符的众数，即可得出将两个子串改成完全相同至少需要改动多少个字符。
结合双指针维护左端点即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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);
}