/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 */

#include <vector>
#include <map>
#include <cstring>
#include <iostream>

#include "optimization.h"

using namespace std;

struct Ukkonen {
	int N, VN; // длина строки, максимальное число вершин
	vector<map<char,int>> t; // t[v][c] = где кончается ребро из "v" по символу "c"
	vector<int> l, r, p, suf; // ребро p[v] -> v это отрезок [l[v], r[v]) исходной строки
	int vn; // число вершин, изначально есть фиктивная=0 и корень=1

	Ukkonen(const char *s) : N(strlen(s)), VN(2 * N + 2), t(VN), l(VN), r(VN), p(VN), suf(VN), vn(2) {
		int v = 1, pos = 0; // идём по ребру из p[v] в v, сейчас стоим в pos
		l[1] = -1; // ребро 0->1: [l,r) = [-1,0)
		for (int i = 0; i < 256; i++)
			t[0][i] = 1; // 0 = фиктивная, 1 = корень
		for (int n = 0; s[n]; n++) {
			char c = s[n];
			auto new_leaf = [&](int v) {
				p[vn] = v, l[vn] = n, r[vn] = N, t[v][c] = vn++;
			};
			go:;
			if (r[v] <= pos) {
				if (!t[v].count(c)) {
					new_leaf(v), v = suf[v], pos = r[v];
					goto go;
				}
				v = t[v][c], pos = l[v] + 1;
			} else if (c == s[pos]) {
				pos++;
			} else {
				int x = vn++;
				l[x] = l[v], r[x] = pos, l[v] = pos;
				p[x] = p[v], p[v] = x;
				t[p[x]][s[l[x]]] = x, t[x][s[pos]] = v;
				new_leaf(x);
				v = suf[p[x]], pos = l[x];
				while (pos < r[x])
					v = t[v][s[pos]], pos += r[v] - l[v];
				suf[x] = (pos == r[x] ? v : vn);
				pos = r[v] - (pos - r[x]);
				goto go;
			}
		}
	}
};

int main() {
	string s;
	cin >> s;
	Ukkonen u(s.c_str()); // или readWord(s) и u(s)
}