[Spoj] ADASTRNG - Ada and Substring

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : ADASTRNG - Ada and Substring
Source            : Spoj
Category          : String
Algorithm         : Suffix Automaton
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll          long long
 
static const int maxn = 5e5 + 5;
 
struct state {
    int len, link;
    map <char, int> next;
} st[maxn*2];
 
int sz, last;
ll dp[maxn*2];
 
void init()
{
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
    ++sz;
//    for (int i = 0; i < maxn*2; i++)
//    {
//        st[i].next.clear();
//        dp[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.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[cur].link = st[q].link = clone;
        }
    }
    last = cur;
}
 
 
ll distinct_sub_string(int ver)
{
    ll tp = 1;
    if (dp[ver] != -1)
        return dp[ver];
    map <char, int>::iterator it;
    for (it=st[ver].next.begin(); it != st[ver].next.end(); it++)
    {
        tp += distinct_sub_string(it->second);
    }
    dp[ver] = tp;
    return dp[ver];
}
 
ll Count[30];
 
void getAns()
{
       for (auto it : st[0].next)
       {
              char ch = it.first;
              int ver = it.second;
              Count[ch - 'a'] = dp[ver];
       }
}
 
char s[maxn];
 
int main()
{
       //freopen("in.txt", "r", stdin);
 
       scanf("%s", s);
       int len = strlen(s);
       init();
       for (int i = 0; i < len; i++) sz_extend(s[i]);
       memset(dp, -1, sizeof dp);
       ll ans = distinct_sub_string(0);
       getAns();
       for (int i = 0; i < 26; i++)
       {
              printf("%lld", Count[i]);
              printf(i == 25 ? "\n" : " ");
       }
}