Problem 0528 : Common Sub-String

共通部分文字列
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0528

• 問題概要

二つの文字列における共通な部分文字列の長さを答えよ

• 解法

この問題での共通部分文字列の定義だと、
片方の文字列をいくつかずらしたときに、もう片方の文字列と一致する長さを求めればいい。
CDABC　と　CCCCCCCCCABC
だと、
二つめの文字列をずらした、CCABC　と　CDABC　という文字列が
ABCという三つれんぞくで一致するので答えは３。

両方の文字列に対して、ずらすということをすればよい。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;


main(){

  string s1, s2;
  while(cin >> s1 >> s2){
    int ans = 0;
    rep(i, s1.length()){
      string tmp = s1.substr(i, s1.length() - i);
      int cnt = 0;
      rep(j, min(tmp.length(), s2.length())){
	if(tmp[j] == s2[j])cnt++;
	else cnt = 0;
	ans = max(ans, cnt);
      }
    } 
    rep(i, s2.length()){
      string tmp = s2.substr(i, s2.length() - i);
      int cnt = 0;
      rep(j, min(tmp.length(), s1.length())){
	if(tmp[j] == s1[j])cnt++;
	else cnt = 0;
	ans = max(ans, cnt);
      }
    }
    cout << ans << endl;
  }
}