#include #include #include using namespace std; /* Atomic structure representing all possible subsequences of given string */ struct SeqTree { string target; struct SeqTreeNode { vector children; char chr; SeqTreeNode(char c = '\0') : chr(c) {} SeqTreeNode(string s) : chr(s[0]) { for(int i = 1; i < s.length(); i++) children.push_back(SeqTreeNode (s.substr(i))); } SeqTreeNode intersect(SeqTreeNode n) { SeqTreeNode res; if(chr == n.chr) res.chr = chr; for(auto i: children) for(auto j: n.children) if(i.chr == j.chr) res.children.push_back(i.intersect(j)); return res; } int deepSize() { int res = 0; for(auto c: children) res = max(res, c.deepSize()); return ++res; } SeqTreeNode longest() { SeqTreeNode res(*this); int deep = 0; for(int i = 0; i < res.children.size(); i++) { res.children[i] = res.children[i].longest(); deep = max(deep, res.children[i].deepSize()); } for(int i = 0; i < res.children.size(); i++) if(res.children[i].deepSize() != deep) res.children.erase(res.children.begin() + i--); return res; } string word() { if(children.empty()) return string() + chr; else return chr + children[0].word(); } } root; SeqTree(string target) : target(target), root("@" + target) {} void show(SeqTreeNode node, string pre = "> ") { pre += node.chr; for(auto n: node.children) { show(n, pre); } cout << pre << endl; } vector all(SeqTreeNode node) { vector res; for(auto c: node.children) { vector tmp = all(c); res.insert(res.end(), tmp.begin(), tmp.end()); } if(node.chr != '\0') { for(int i = 0; i < res.size(); i++) res[i] = node.chr + res[i]; res.push_back(node.chr + string()); } return res; } }; int main() { string s1, s2; getline(cin, s1); getline(cin, s2); SeqTree seq1(s1), seq2(s2); cout << "string no1: '" << s1 << "'\n"; cout << "string no2: '" << s2 << "'\n"; SeqTree::SeqTreeNode subseq; subseq = seq1.root.intersect(seq2.root); cout << "longest: '" << subseq.longest().word().substr(1) << "'"; return 0; }

longest shared string subsequence