[Codeforces] D. Match & Catch

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Match & Catch
Source            : Codeforces
Category          : String
Algorithm         : Suffix Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e6 + 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);  
}  
  
string s1;  
string s2;  
int len1;  
int len2;  
  
int dfs(int u = 0, int p = -1)  
{  
      int mini = inf;  
      vector <int> go;  
      for (auto it : t[u].next)  
      {  
            char ch = it.first;  
            int v = it.second;  
            if (v == p) continue;  
            go.push_back(v);  
      }  
      int len = go.size();  
      if (len < 2) return mini;  
      if (len == 2)  
      {  
            int pos1 = t[ go[0] ].l;  
            int pos2 = t[ go[1] ].l;  
            if (pos1 > pos2) swap(pos1, pos2);  
            if (t[ go[0] ].r == n && t[ go[1] ].r == n)  
            {  
                  if (pos1 <= len1 and pos2 > len1) return 1;  
                  return mini;  
            }  
      }  
      for (int v : go)  
      {  
            mini = min(mini, t[u].len() + dfs(v, u));  
      }  
      return mini;  
}  
  
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 >> s1 >> s2;  
      len1 = s1.size();  
      len2 = s2.size();  
      s = s1 + "#" + s2 + "$";  
      n = s.size();  
      build_tree();  
      int ans = dfs();  
      if (ans == inf) ans = -1;  
      cout << ans;  
}