srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

aoj 0528 - Common Sub-String

問題

問題概要

共通部分文字列の問題。ただし、連続した文字列でなければならない

解法

単純なdp。文字列s1とs2の両方を何文字目ま見ているかという要素を配列の要素と持つdpを考えればいい。
dp[i][j] = dp[s1のi文字目までで考える][s2のj文字目までで考える] = (連続文字列の長さ)
という配列を考える。あとは漸化式を立てればいい。漸化式は考えている2つの文字列の末尾が一致しているかどうかで場合を分けて丁寧に考察すればわかる。   DAGで考える。DAGの頂点として、2つの文字列を持って入れば、文字列の長さを伸ばす方向に有向辺を引くことでDAGが作れる。そして、辺の重みは末尾の文字が一致しているなら1で、一致していないなら、0初期化の命令を入れればいい。

ミス

はじめ、連続文字列ではないと誤読、問題読んでないだけ。

コード

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int dp[4001][4001];
int main(void){
    while(1){
        string s1, s2; cin >> s1 >> s2;
        if(s1 == "") return 0;
        int s1size = s1.size(), s2size = s2.size();
        rep(i, 4001) dp[i][0] = dp[0][i] = 0;
        //dp[i][j] = dp[s1のi文字目まで][s2のj文字目まで] = (連続文字列の長さ)

        int ans = 0;
        rep(i, s1size){
            rep(j, s2size){
                if(s1[i] == s2[j]){
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    ans = max(ans, dp[i + 1][j + 1]);
                }else{
                    dp[i + 1][j + 1] = 0;
                }

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