読者です 読者をやめる 読者になる 読者になる

最長共通部分文字列と最長共通部分列

今日から少し、典型DPを扱ってみようと思う。

最長共通部分文字列(longest common substring)と最長共通部分列(longest common subsequence)。

前者は連続という条件つきで、後者は連続でなくても順序が維持されていればよいというもの。
前者はO( (n+m)min(n,m) )とかそんな感じで、後者はO(nm)。まあ前者はDPではない。

/*
 * longest common substring
 */

#include <iostream>
#include <cstdio>

using namespace std;

int main(int argc, char **argv)
{
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int maxcase_off1=0;
    int maxcase_off2=0;
    int maxcase_len=0;
    for(int off = -(int)s1.size(); off <= (int)s2.size(); off++) {
        int len = 0;
        for(int i = max(off, 0); i < min(s1.size()+off, s2.size()); i++) {
            if(len > maxcase_len) {
                maxcase_off1 = i-len-off;
                maxcase_off2 = i-len;
                maxcase_len = len;
            }
            if(s1[i-off] != s2[i]) {
                len = 0;
            } else {
                len++;
            }
        }
    }
    cout << s1.substr(maxcase_off1, maxcase_len) << endl;
    return 0;
}
/*
 * longest common subsequence
 */

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char **argv)
{
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    vector<vector<pair<int, pair<int, int> > > > dp(s1.size()+1, vector<pair<int, pair<int, int> > >(s2.size()+1));
    for(unsigned int i = 0; i <= s1.size(); i++) {
        for(unsigned int j = 0; j <= s2.size(); j++) {
            if(i==0 || j==0) {
                dp[i][j] = make_pair(0, make_pair(-1, -1));
            } else {
                dp[i][j] = dp[i][j-1];
                if(dp[i][j].first < dp[i-1][j].first) {
                    dp[i][j] = dp[i-1][j];
                }
                if(s1[i-1] == s2[j-1] && dp[i][j].first < dp[i-1][j-1].first+1) {
                    dp[i][j] = make_pair(dp[i-1][j-1].first+1, make_pair(i-1, j-1));
                }
            }
        }
    }
    vector<char> subseq_stack;
    for(unsigned int i=s1.size(), j=s2.size();i>0 && j>0;) {
        pair<int, int> next = dp[i][j].second;
        //make_pair(i,j) = next;
        i = next.first; j = next.second;
        if(i<0 || j<0) break;
        subseq_stack.push_back(s1[i]); // s1[i] == s2[j]
    }
    while(!subseq_stack.empty()) {
        printf("%c", subseq_stack.back());
        subseq_stack.pop_back();
    }printf("\n");
    return 0;
}