最長共通部分文字列と最長共通部分列
今日から少し、典型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; }