[ABC141E] Who Says a Pun?

Who Says a Pun の 传送门

看到两个完全相同的子串，考虑 dp。

设 \(f_{i,j}\) 为从第 \(i\) 项和第 \(j\) 项开始的最长相同子串，则有 \(s_i=s_j\) 时，\(f_{i,j}=\max({f_{i-1,j-1}+1},f_{i,j})\)。

注意，因为两个子串互不重叠，所以 \(f_{i-1,j-1} < j-i\) 时才可以转移状态。

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n,f[N][N],ans;
char a[N];
signed main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)	cin>>a[i];
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j)
			if(a[i]==a[j]&&f[i-1][j-1]<j-i)
				f[i][j]=max(f[i][j],f[i-1][j-1]+1),
				ans=max(ans,f[i][j]);
	cout<<ans;
	return 0;
}