[toph.co] Distinctness

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Distinctness
Source            : toph.co
Category          : String
Algorithm         : Suffix Automata
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()
#define ll             long long
 
static const int maxn = 1e5 + 5;
 
string A;
 
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 ll sz_extend(char c)
{
      ll sum = 0;
      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;
                  }
                  sum = sum - (st[q].len - st[ st[q].link ].len);
                  st[q].link = st[cur].link = clone;
                  sum = sum + st[q].len - st[ st[q].link ].len;
                  sum = sum + st[clone].len - st[ st[clone].link ].len;
            }
      }
      sum = sum + st[cur].len - st[ st[cur].link ].len;
      last = cur;
      return sum;
}
 
int main()
{
      FAST;
 
      init();
 
      cin >> A;
      ll tsub = 0;
      for (char ch : A)
      {
            tsub += sz_extend(ch);
            cout << tsub << endl;
      }
}