AOJ : 0528 - 共通部分文字列 (Common Sub-String)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0528&lang=jp
日本語の問題文なので省略です

アルゴリズム

文字列Aの先頭を1文字ずつ削りながら、文字列Bと一致する文字列を探します。
そのあと、同じことを文字列Bの文字を削りながら行います。
この工程の中で、一番最長一致した文字列の長さが答えです。
（説明がかなり適当）

プログラム

#include <stdio.h>
#include <string.h>

char a[4004],b[4004];

int solve(char *s,char *t,int lenS,int lenT){
  int i,j;
  int count = 0;
  int res = 0;

  for(i=j=0;i<lenS && j<lenT;i++,j++){
    if(s[i] == t[j]){
      count++;
    }
    else{
      if(res < count) res = count;
      count = 0;
    }
  }

  if(res < count) res = count;
  return res;
}

int main(void){
  int i,j;
  int lenA,lenB;
  int ans,tmp;

  while(scanf("%s%s",a,b) != EOF){
    lenA = strlen(a);
    lenB = strlen(b);
    ans = 0;

    //Aの先頭のi文字を削った文字列と,Bを比較
    for(i=0;i<lenA;i++){
      tmp = solve(&a[i],b,lenA-i,lenB);
      if(ans < tmp) ans = tmp;
    }

    //Bの先頭のi文字を削った文字列と,Aを比較
    for(i=0;i<lenB;i++){
      tmp = solve(&b[i],a,lenB-i,lenA);
      if(ans < tmp) ans = tmp;
    }

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

  return 0;
}