[toph.co] Another Dirty String

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Another Dirty String
Source            : toph.co
Category          : String, Data Structure
Algorithm         : Suffix Automata, KMP, Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define FAST       ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
 
#define vi         vector <int>
#define eb         emplace_back
#define sze(a)      (int)a.size()
 
static const int maxn = 1e5 + 5;
 
string A, B, C;
int occ[maxn], cumocc[maxn];
 
inline vi longestPreffixSuffix(string pat)
{
      vi lps;
      lps.eb(0);
      int i = 1, j = 0;
      int len = sze(pat);
      while (i < len)
      {
            if (pat[i] == pat[j])
            {
                  i++;
                  j++;
                  lps.eb(j);
            }
            else
            {
                  if (j)
                  {
                        j = lps[j-1];
                  }
                  else
                  {
                        i++;
                        lps.eb(0);
                  }
            }
      }
      return lps;
}
 
inline void kmp(string text, string pat)
{
      int lenText = sze(text);
      int lenPat = sze(pat);
      vi lps = longestPreffixSuffix(pat);
      int i = 0, j = 0;
      while (i < lenText)
      {
            if (text[i] == pat[j])
            {
                  i++;
                  j++;
            }
            if (j == lenPat)
            {
                  occ[i-1-lenPat+1] = 1;
                  j = lps[j-1];
            }
            else if (i < lenText && text[i] != pat[j])
            {
                  if (j) j = lps[j-1];
                  else i++;
            }
      }
}
 
struct segmentTree
{
      int lastocc;
      void assignLeaf(int val, int pos)
      {
            lastocc = -1;
            if (val == 1) lastocc = pos;
      }
      void marge(segmentTree l, segmentTree r)
      {
            if (l.lastocc > r.lastocc) lastocc = l.lastocc;
            else if (l.lastocc < r.lastocc) lastocc = r.lastocc;
            else lastocc = l.lastocc;
      }
} tree[maxn << 2];
 
inline void build(int node, int a, int b)
{
      if (a == b)
      {
            tree[node].assignLeaf(occ[a], a);
            return;
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      build(lft, a, mid);
      build(rgt, mid+1, b);
      tree[node].marge(tree[lft], tree[rgt]);
}
 
inline segmentTree query(int node, int a, int b, int i, int j)
{
      if (a > b || a > j || b < i)
      {
            segmentTree nul;
            nul.lastocc = -1;
            return nul;
      }
      if (a >= i && b <= j) return tree[node];
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      segmentTree p, q, res;
      p = query(lft, a, mid, i, j);
      q = query(rgt, mid+1, b, i, j);
      res.marge(p, q);
      return res;
}
 
struct state
{
      int len, link;
      map <char, int> next;
};
 
state st[maxn << 1];
 
int sz, last;
 
inline void init()
{
      sz = last = 0;
      st[0].len = 0;
      st[0].link = -1;
      st[0].next.clear();
      ++sz;
      for (int i = 1; i < (maxn << 1); i++)
      {
            st[i].len = 0;
            st[i].link = 0;
            st[i].next.clear();
      }
}
 
inline void sz_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;
}
 
 
inline int LCS(string A, string B, string C)
{
      int lenA = sze(A);
      int lenB = sze(B);
      int lenC = sze(C);
 
      memset(occ, 0, sizeof occ);
      memset(cumocc, 0, sizeof cumocc);
      memset(tree, -1, sizeof tree);
 
      kmp(B, C);
 
      build(1, 0, lenB-1);
 
      init();
      for (int i = 0; i < lenA; i++) sz_extend(A[i]);
 
      int v = 0;
      int l = 0;
      int best = 0;
      int bestPos = 0;
 
      for (int i = 0; i < lenB; i++)
      {
            while (v && !st[v].next.count(B[i]))
            {
                  v = st[v].link;
                  l = st[v].len;
            }
            if (st[v].next.count(B[i]))
            {
                  v = st[v].next[ B[i] ];
                  l++;
            }
 
            int newl = 0;
            if (l < lenC)
            {
                  newl = l;
            }
            else
            {
                  int bgn = i - l + 1;
                  int edd = i - lenC + 1;
                  segmentTree q = query(1, 0, lenB-1, bgn, edd);
                  if (q.lastocc == -1)
                  {
                        newl = l;
                  }
                  else
                  {
                        newl = i - q.lastocc;
                  }
            }
            if (newl > best)
            {
                  best = newl;
                  bestPos = i;
            }
      }
//      cout << B.substr(bestPos - best + 1, best) << endl;
      return best;
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
      FAST;
 
      int tc;
      cin >> tc;
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            cin >> A >> B >> C;
            cout << LCS(A, B, C) << endl;
      }
}