Problem 6: Suffix Automaton

Problem Statement: Given a string S, construct its suffix automaton and then answer queries about the number of distinct substrings present in S.

Input

A single string S is given in the first line.

Output

Print the number of distinct substrings of S.

Examples


Input:
ababa

Output:
9

Solution Explanation

Method 1: Build the suffix automaton incrementally while processing each character, then count distinct substrings using the difference in lengths between states and their links. Method 2: The problem can also be solved by constructing the suffix tree and then counting distinct substrings from the edge labels, though this method is more complex to implement.

Solution in C++


#include 
#include 
#include 
#include 
#include 
using namespace std;

struct State {
    int len, link;
    map next;
};

vector st;
int sz, last;

void sa_init(int n){
    st.resize(2*n);
    st[0].len = 0;
    st[0].link = -1;
    sz = 1;
    last = 0;
}

void sa_extend(char c){
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p = last;
    for(; 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;
}

int main(){
    string s;
    cin >> s;
    sa_init(s.size());
    for(char c : s)
        sa_extend(c);
    long long distinct = 0;
    for (int i = 1; i < sz; i++) {
        distinct += st[i].len - st[st[i].link].len;
    }
    cout << distinct;
    return 0;
}