[Toph] Simple As a Substring!

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Simple As a Substring!
Source            : Toph
Category          : String
Algorithm         : Suffix Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 5e6 + 5;  
static const int inf  = 1e9 + 5;  
  
struct Node  
{  
      int l;  
      int r;  
      int par;  
      int link;  
      map <char,int> next;  
      Node(int l = 0, int r = 0, int par = -1)  
            : l(l)  
            , r(r)  
            , par(par)  
            , link(-1) {}  
  
      int len()  
      {  
            return r - l;  
      }  
      int &get(char c)  
      {  
            if (!next.count(c)) next[c] = -1;  
            return next[c];  
      }  
};  
  
Node t[maxn];  
string s;  
int sz;  
int n;  
  
struct state  
{  
      int v, pos;  
      state(int v, int pos) : v(v), pos(pos) {}  
};  
  
state ptr (0, 0);  
  
state go(state st, int l, int r)  
{  
      while (l < r)  
      {  
            if (st.pos == t[st.v].len())  
            {  
                  st = state (t[st.v].get( s[l] ), 0);  
                  if (st.v == -1) return st;  
            }  
            else  
            {  
                  if (s[ t[st.v].l + st.pos ] != s[l])  
                        return state (-1, -1);  
                  if (r - l < t[st.v].len() - st.pos)  
                        return state (st.v, st.pos + r-l);  
                  l += t[st.v].len() - st.pos;  
                  st.pos = t[st.v].len();  
            }  
      }  
      return st;  
}  
  
int split(state st)  
{  
      if (st.pos == t[st.v].len())  
            return st.v;  
      if (st.pos == 0)  
            return t[st.v].par;  
      Node v = t[st.v];  
      int id = sz++;  
      t[id] = Node(v.l, v.l + st.pos, v.par);  
      t[v.par].get(s[v.l]) = id;  
      t[id].get(s[v.l + st.pos]) = st.v;  
      t[st.v].par = id;  
      t[st.v].l += st.pos;  
      return id;  
}  
  
int get_link(int v)  
{  
      if (t[v].link != -1)  
            return t[v].link;  
      if (t[v].par == -1)  
            return 0;  
      int to = get_link(t[v].par);  
      return t[v].link = split(go(state(to, t[to].len()), t[v].l + (t[v].par == 0), t[v].r));  
}  
  
void tree_extend(int pos)  
{  
      for(;;)  
      {  
            state nptr = go(ptr, pos, pos+1);  
            if (nptr.v != -1)  
            {  
                  ptr = nptr;  
                  return;  
            }  
            int mid = split(ptr);  
            int leaf = sz++;  
            t[leaf] = Node(pos, n, mid);  
            t[mid].get(s[pos]) = leaf;  
            ptr.v = get_link(mid);  
            ptr.pos = t[ptr.v].len();  
            if (!mid) break;  
      }  
}  
  
void build_tree()  
{  
      sz = 1;  
      for (int i = 0; i < n; i++) tree_extend(i);  
}  
  
int mark[maxn];  
int counter[maxn][11];  
int numstr;  
  
void dfs(int u = 0)  
{  
      if (t[u].r == n)  
      {  
            counter[u][ mark[ t[u].l ] ]++;  
            return;  
      }  
      for (auto it : t[u].next)  
      {  
            int v = it.second;  
            dfs(v);  
            for (int i = 0; i < numstr; i++) counter[u][i] += counter[v][i];  
      }  
}  
  
int solve(int u = 0)  
{  
      int one = 0;  
      for (int i = 0; i < numstr; i++)  
      {  
            if (counter[u][i] == 0) return -inf;  
            if (counter[u][i] == 1) ++one;  
      }  
      if (one == numstr) return t[u].len();  
      int maxi = -inf;  
      for (auto it : t[u].next)  
      {  
            int v = it.second;  
            int go = t[u].len() + solve(v);  
            if (go > maxi) maxi = go;  
      }  
      return maxi;  
}  
  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> numstr;  
      char asign = 'A';  
      for (int i = 1; i <= numstr; i++)  
      {  
            string str;  
            cin >> str;  
            s += str;  
            if (i < numstr) s += asign;  
            asign++;  
      }  
      s += '$';  
      n = s.size();  
      int v = 0;  
      for (int i = 0; i < n; i++)  
      {  
            mark[i] = v;  
            if (!islower(s[i])) v++;  
      }  
      build_tree();  
      dfs();  
      cout << max(0, solve());  
}