1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

#include <iostream>
#include <stdio.h>
#include <string>

const int oo = 1<<25;
const int ALPHABET_SIZE = 256;
const int MAXN = 5000;

using namespace std;

int root, last_added, pos, needSL, remainder,
	active_node, active_e, active_len;

struct node {
/*
   There is no need to create an "Edge" struct.
   Information about the edge is stored right in the node.
   [start; end) interval specifies the edge,
   by which the node is connected to its parent node.
*/

	int start, end, slink;
	int next[ALPHABET_SIZE];	

	int edge_length() {
		return min(end, pos + 1) - start;
	}
};

node tree[2*MAXN];
char text[MAXN];

int new_node(int start, int end = oo) {
	node nd;
	nd.start = start;
	nd.end = end;
	nd.slink = 0;
	for (int i = 0; i < ALPHABET_SIZE; i++)
		nd.next[i] = 0;
	tree[++last_added] = nd;
	return last_added;
}

char active_edge() {
	return text[active_e];
}

void add_SL(int node) {
	if (needSL > 0) tree[needSL].slink = node;
	needSL = node;
}

bool walk_down(int node) {
	if (active_len >= tree[node].edge_length()) {
		active_e += tree[node].edge_length();
		active_len -= tree[node].edge_length();
		active_node = node;
		return true;
	}
	return false;
}

void st_init() {
	needSL = 0, last_added = 0, pos = -1, 
	remainder = 0, active_node = 0, active_e = 0, active_len = 0;
	root = active_node = new_node(-1, -1);
}

void st_extend(char c) {
	text[++pos] = c;
	needSL = 0;
	remainder++;
	while(remainder > 0) {
		if (active_len == 0) active_e = pos;
		if (tree[active_node].next[active_edge()] == 0) {
			int leaf = new_node(pos);
			tree[active_node].next[active_edge()] = leaf;
			add_SL(active_node); //rule 2
		} else {
			int nxt = tree[active_node].next[active_edge()];
			if (walk_down(nxt)) continue; //observation 2
			if (text[tree[nxt].start + active_len] == c) { //observation 1
				active_len++;
				add_SL(active_node); //observation 3
				break;
			}
			int split = new_node(tree[nxt].start, tree[nxt].start + active_len);
			tree[active_node].next[active_edge()] = split;
			int leaf = new_node(pos);
			tree[split].next[c] = leaf;
			tree[nxt].start += active_len;
			tree[split].next[text[tree[nxt].start]] = nxt;
			add_SL(split); //rule 2
		}
		remainder--;
		if (active_node == root && active_len > 0) { //rule 1
			active_len--;
			active_e = pos - remainder + 1;
		} else
			active_node = tree[active_node].slink > 0 ? tree[active_node].slink : root; //rule 3
	}
}

int main() {
	//
	return 0;
}