共通部分文字列

問題

情報オリンピックJOI2008本選
AOJ0528

2つの文字列が与えられたとき、両方の文字列に含まれる文字列のうち最も長いものの長さを返す。

考え方

最も単純な方法は、片方の部分文字列を作ってそれがもう片方に含まれるかを探す方法。
しかし、これではO(n^4)になってしまうので、文字列の長さが長いと時間がかかりすぎてしまう。

上記の方法では、無駄な文字列比較が多発している。
なので、各文字列の比較開始の場所を決め、そこから何文字連続して同じ文字になるかをカウント。
これはO(n^3)なので、少し速い。

実はこれでも無駄な比較があり、同じ部分を2回以上比較してたりしている。
片方の文字列を固定して、もう片方をずらしながら重なる部分を見ることで、無駄をなくすことができる。

比較の流れを表すと、

---------------------------------
ABCDEF         ←ずらす文字列(s)
_____ABCBA_____←固定する文字列(t)
     x         ←同じ文字かどうか
---------------------------------
   ABCDE
_____ABCBA_____
     xxxx
---------------------------------
     ABCDEF
_____ABCBA_____
     oooxx
---------------------------------
      ABCDEF
_____ABCBA_____
      xxxx
---------------------------------
         ABCDEF
_____ABCBA_____
      xxxo

のような感じで、oが一番連続するのは3なので、答えは3。

以下、コード。(AOJ0528 Accept)

#include <iostream>
using namespace std;

/*
//O(n^4)の解法
//片方の部分文字列を作成し、それがもう片方に含まれるかどうかをチェック
int calc(string &s, string &t){
  int len = min(s.length(), t.length());

  for(int l=len; l>0; l--){
    for(int pos=0; pos<s.length()-l+1; pos++){
      string u = s.substr(pos, l);
      if(t.find(u) != string::npos){
        return u.length();
      }
    }
  }
  return 0;
}
*/

/*
//O(n^3)の解法
//両方の文字列についてスタート位置を決め、何文字合っているかをチェック
int calc(string &s, string &t){
  int ret = 0;
  
  for(int i=0; i<s.length(); i++){
    for(int j=0; j<t.length(); j++){
      //iは文字列sのスタート位置、jは文字列tのスタート位置
      for(int k=0; ; k++){
        if(i+k<s.length() && j+k<t.length()){
          if(s[i+k] == t[j+k]){
            ret = max(ret, k+1);
          }else{
            break;
          }
        }else{
          break;
        }
      }
    }
  }
  return ret;
}
*/

//O(n^2)の解法
//どちらかの文字列を固定し、もう片方の文字列を左からずらしながら連続する文字列の長さを比較
//   ABCDABCD       ←ずらす文字列
//     ABABCABDB    ←固定する文字列
//     xxooox       ←同じ文字(連続するoの数を数える)
int calc(string &s, string &t){
  string nt = "";
  for(int i=0; i<s.length(); i++) nt += "*"; //ダミー
  nt += t + nt; //文字列tの前後にダミーの文字("*")を入れることで、条件分岐などをなくした

  int ret = 0;
  for(int i=0; i<nt.length()-s.length(); i++){
    int tmp = 0;
    for(int j=0; j<s.length(); j++){
      if(s[j]==nt[i+j]) tmp++;
      else tmp = 0;
      ret = max(ret, tmp);
    }
  }
  return ret;
}

int main(){
  string s, t;
  
  while(cin >> s >> t){
    cout << calc(s, t) << endl;
  }
  return 0;
}