[UVa] 760 - DNA Sequencing

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 760 - DNA Sequencing
Source            : UVa Online Judge
Category          : String
Algorithm         : Suffix Automaton
Verdict           : Accepted 
Problem Type : LCS of 2 String
 
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <memory.h>
#include <functional>
#include <numeric>
 
using namespace std;
 
#define READ                                 freopen("in.txt", "r", stdin)
#define WRITE                                freopen("out.txt", "w", stdout)
 
#define FAST                                 ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
 
#define All(v)                               v.begin(), v.end()
#define SZ(a)                                a.size()
#define Sort(v)                              sort(All(v))
#define ED(v)                                Sort(v), v.erase(unique(All(v), v.end())
#define Common(a, b)                         Sort(v), Sort(b), a.erase(set_intesection(All(a), All(b), a.begin(), a.end()))
#define UnCommon(a, b)                       Sort(v), Sort(b), a.erase(set_symmetric_difference(All(a), All(b), All(a)))
 
 
#define max3(a, b, c)                        max(a, max(b, c))
#define min3(a, b, c)                        min(a, min(b, c))
#define maxAll(v)                            *max_element(All(v))
#define minAll(v)                            *min_element(All(v))
 
 
#define AllUpper(a)                          transform(All(a), a.begin(), :: toupper)
#define AllLower(a)                          transform(All(a), a.begin(), :: tolower)
#define Rev(a)                               reverse(All(a))
 
 
#define memo(a, b)                           memset(a, b, sizeof(a))
 
#define ff                                   first
#define ss                                   second
#define pb                                   push_back
#define mk                                   make_pair
 
#define inf2                                 1 << 28
 
template <typename T>string toString (T Number)    { stringstream st; st << Number; return st.str(); }
int toInteger (string s)                           { int p; istringstream st(s); st>>p ; return p; }
 
//int dr[] = {1, -1, 0, 0};               // 4 Direction
//int dc[] = {0, 0, 1, -1};
 
//int dr[] = {0, 0, 1, -1, 1, 1, -1, -1};  // 8 Direction
//int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};
 
//int dr[] = {-1, 1, -2, -2, -1, 1, 2, 2}; // knight Moves
//int dc[] = {-2, -2, -1, 1, 2, 2, 1, -1};
 
 
#define Exp                                  exp(1.0)
#define PIE                                  2*acos(0.0)
#define Sin(a)                               sin(((a)*PI)/180.0)
#define mod                                  1000000007
#define EPS                                  1e-9
 
#define sqr(a)                               ((a)*(a))
#define gcd(a,b)                              __gcd(a,b)
#define lcm(a,b)                             (a*(b/gcd(a,b)))
 
 
typedef long long                            ll;
 
 
static const int mx = 1e5 + 5;
static const int inf = 1e7;
 
static const int MAXN = 3300;
 
struct state 
{
    int len, link; 
    map <char, int> next;
}st[MAXN << 1];
 
int sz, last;
 
void init()
{
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
    //clear the structure
    for (int i=0; i < (MAXN<<1); i++)
    {
        st[i].next.clear();
    }
}
 
void sz_extend(char c)
{
    int curr = sz++;
    st[curr].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] = curr;
    if (p == -1)
        st[curr].link = 0;
    else
    {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len)
            st[curr].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[curr].link = clone;
        }
    }
    last = curr;
}
 
int lcsLen[MAXN];
 
int LCS(string s, string t)
{
    init();
    int len_s = s.length();
    int len_t = t.length();
    for (int i = 0; i < len_s; i++)
    {
        sz_extend(s[i]);
    }
    int v = 0;
    int l = 0;
    int best = 0;
    int bestPos = 0;
    for (int i=0; i<len_t; 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++;
        }
        lcsLen[i] = l;
        if (l > best)
        {
            best = l;
            bestPos = i;
        }
    }
    //return t.substr(bestPos-best+1, best); // LCS
    return best;
}
 
int main()
{
    //READ;
 
    FAST;
 
    bool flag = false;
    string s, t;
    while (cin >> s >> t)
    {
        if (flag) cout << endl;
        flag = true;
        int maxLCS = LCS(s, t);
        if (maxLCS == 0)
        {
            cout << "No common sequence." << endl;
            continue;
        }
        set <string> vec;
        int len = t.size();
        for (int i = len - 1; i >= 0; i--)
        {
            if (lcsLen[i] != maxLCS)
            {
 
            }
            else
            {
                vec.insert(t.substr(i - maxLCS + 1, maxLCS));
            }
        }
        for (auto ele : vec) cout << ele << endl;
        vec.clear();
    }
}