E06 线性DP 最长公共子串

// 线性DP O(n^2)
#include<bits/stdc++.h>
using namespace std;

const int N=5005;
char a[N],b[N];
int n,m,f[N][N],ans,pos;

int main(){
  cin>>a+1>>b+1;
  n=strlen(a+1); m=strlen(b+1);
  
  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
      if(f[i][j]>ans) ans=f[i][j], pos=i;
    }
  }
  cout<<ans<<"\n";
  for(int i=pos-ans+1;i<=pos;i++) cout<<a[i];
  return 0;
}