[Spoj] DISUBSTR - Distinct Substrings

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DISUBSTR - Distinct Substrings
Source            : Spoj
Category          : String
Algorithm         : Suffix Automaton
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
const int mx = 1e6 + 5;
 
int d[mx*2];
 
struct state {
    int len, link;
    map <char, int> next;
}st[mx*2];
 
int sz, last;
 
void init()
{
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
    for (int i=0; i<mx*2; i++)
    {
        st[i].next.clear();
        d[i] = 0;
    }
}
 
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[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[cur].link = st[q].link = clone;
        }
    }
    last = cur;
}
 
int distinct_sub_string(int ver)
{
    int tp = 1;
    if (d[ver]) return d[ver];
    map <char, int>::iterator it;
    for (it=st[ver].next.begin(); it!=st[ver].next.end(); it++)
    {
        tp += distinct_sub_string(it->second);
    }
    d[ver] = tp;
    return d[ver];
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc;
    cin >> tc;
    for (int tcase=1; tcase<=tc; tcase++)
    {
        string s;
        cin >> s;
        init();
        int len = s.length();
        for (int i=0; i<len; i++)
        {
            sz_extend(s[i]);
        }
        int subString = distinct_sub_string(0);
        cout << (subString - 1) << endl;
    }
    return 0;
}