Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <string>
- #include <map>
- using namespace std;
- const int MAXLEN = 100000;
- int sz, last;
- struct state {
- int len, link;
- map<char, int> next;
- };
- state st[MAXLEN * 2];
- void init() {
- sz = last = 0;
- st[0].len = 0;
- st[0].link = -1;
- ++sz;
- }
- void extend(char c) {
- int cur = sz++;
- st[cur].len = st[last].len + 1;
- int p;
- for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
- st[p].next[c] = cur;
- if (p == -1)
- st[cur].link = 0;
- else {
- int q = st[p].next[c];
- if (st[p].len + 1 == st[q].len)
- st[cur].link = q;
- else {
- int clone = sz++;
- st[clone].len = st[p].len + 1;
- st[clone].next = st[q].next;
- st[clone].link = st[q].link;
- for (; p != -1 && st[p].next[c] == q; p = st[p].link)
- st[p].next[c] = clone;
- st[q].link = st[cur].link = clone;
- }
- }
- last = cur;
- }
- string lcs(string s, string t) {
- init();
- for (int i = 0; i < (int) s.length(); ++i)
- extend(s[i]);
- int v = 0, l = 0,
- best = 0, bestpos = 0;
- for (int i = 0; i < (int) t.length(); ++i) {
- while (v && !st[v].next.count(t[i])) {
- v = st[v].link;
- l = st[v].len;
- }
- if (st[v].next.count(t[i])) {
- v = st[v].next[t[i]];
- ++l;
- }
- if (l > best)
- best = l, bestpos = i;
- }
- return t.substr(bestpos - best + 1, best);
- }
- int main(){
- ifstream fin("common.in");
- ofstream fout("common.out");
- string first, second;
- fin >> first >> second;
- fout << lcs(first, second);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement