第７回日本情報オリンピック 本選 「共通部分文字列」

解法は顕著。

もし文字a[i] == b[j]だったらdp[i][j] = dp[i-1][j-1] + 1;をすることによって連続する文字列を求める。常にdp[i][j]の値をチェックし、最大のものが解。

計算量はO(N^2).

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[4003][4003] = {0};
int main(){

  
  char a[4002],b[4002];
  
  while(cin >> a >> b){
  int ans = 0;
  memset(dp,0,sizeof(dp));

  int alen = strlen(a);
  int blen = strlen(b);
  
  for(int i = 1;i <= alen;i++){
    for(int j = 1;j <= blen;j++){
      if(a[i-1] == b[j-1]){
	dp[i][j] = dp[i-1][j-1] + 1;
	ans = max(ans,dp[i][j]);
      }
    }
  }

  printf("%d\n",ans);
  
  }
  
  return 0;
  
}