#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <fstream>

using namespace std;

struct State
{
    int pos;
    int len;
    int link;
    unordered_map<char,int> transitions;

    State(int pos = 0, int len = 0, int link = -1,const unordered_map<char,int>& tr = unordered_map<char,int>()):pos(pos),len(len),link(link),transitions(tr)
    {
    }
};

struct SuffixAutomata
{
    vector<State> states;
    int numOfTransitions;
    unordered_set<int> finalStates;

    SuffixAutomata(const string& w);
};

SuffixAutomata::SuffixAutomata(const string& w)
{
    int len = w.size();
    states = vector<State>();
    finalStates = unordered_set<int>();
    numOfTransitions = 0;
    State last;
    states.push_back(last);
    int numStates = 0;
    for(int i = 0; i < len; ++i)
    {
        ++numStates;
        State curr(numStates,last.len + 1);
        char c = w[i];
        State p = last;
        int t = p.pos;

        while(t > -1 && states[t].transitions.find(c) == states[t].transitions.end())
        {
            states[t].transitions[c] = curr.pos;
            numOfTransitions++;
            t = states[t].link;
        }
        if(t == -1)
        {
            curr.link = 0;
            last = curr;
            states.push_back(curr);
            continue;
        }
        else
        {
            p = states[t];
            int q = p.transitions[c];
            State qState = states[q];
            if(p.len + 1 == qState.len)
            {
                curr.link = q;
                last = curr;
                states.push_back(curr);
                continue;
            }
            ++numStates;
            State clone(numStates,p.len + 1, qState.link);
            clone.transitions = qState.transitions;
            numOfTransitions += qState.transitions.size();
            curr.link = numStates;
            qState.link = numStates;
            states.push_back(curr);
            while(t > -1 && states[t].transitions[c] == q)
            {
                states[t].transitions.erase(c);
                states[t].transitions[c] = clone.pos;
                t = states[t].link;
            }
            states.push_back(clone);
        }
        last = curr;
    }
    while(last.link > -1)
    {
        finalStates.insert(last.pos);
        last = states[last.link];
    }
    finalStates.insert(last.pos);
}

bool isSuffix(const SuffixAutomata& a, const string& s)
{
    int q = 0;
    for(int i = 0; i < s.size(); i++)
    {
        if(a.states[q].transitions.find(s[i]) == a.states[q].transitions.end())
        {
            return false;
        }

        q = a.states[q].transitions.at(s[i]);
    }

    if(a.finalStates.find(q) != a.finalStates.end())
    {
        return true;
    }

    return false;
}

bool isInfix(const SuffixAutomata& a, const string& s)
{
    int q = 0;
    for(int i = 0; i < s.size(); i++)
    {
        if(a.states[q].transitions.find(s[i]) == a.states[q].transitions.end())
        {
            return false;
        }

        q = a.states[q].transitions.at(s[i]);
    }

    return true;
}

int main()
{
    string w;
    cin >> w;

    SuffixAutomata a(w);

    cout << "Number of states = " << a.states.size() << endl;
    cout << "Number of transitions = " << a.numOfTransitions << endl;

    cout << "Printing transitions : \n";
    for(int i = 0; i < a.states.size(); i++)
    {
        for(auto it = a.states[i].transitions.begin(); it != a.states[i].transitions.end(); it++)
        {
            cout << i << " " << it->first << " " << it->second << endl;
        }
    }
    cout << "Number of final states = " << a.finalStates.size() << endl;

    for(auto it = a.finalStates.begin(); it != a.finalStates.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;


    return 0;
}