import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class Node2 {
int valid;
int[] children;
int pi;
ArrayList indexes;
Node2() {
valid = -1;
children = new int[26];
for (int i = 0; i < 26; i++) {
children[i] = -1;
}
pi = -1;
indexes = new ArrayList();
}
}
public class _Aho_corasick_ {
static ArrayList trie = new ArrayList<>();
static int init() {
Node2 x = new Node2();
trie.add(x);
return (int) trie.size() - 1;
}
static void add(int Node2, String s, int index, int string_index) {
if (index == s.length()) {
trie.get(Node2).valid = string_index;
return;
}
int c = s.charAt(index) - 'A';
if (trie.get(Node2).children[c] == -1) {
int next = init();
trie.get(Node2).children[c] = next;
}
add(trie.get(Node2).children[c], s, index + 1, string_index);
}
public static void main(String args[]) {
int root = init();
int n = 5;
String[] a = { "ABAB", "AD", "ABC", "BCD", "ABABC" };
for (int i = 0; i < n; i++) {
add(root, a[i], 0, i);
}
Queue q = new LinkedList<>();
trie.get(root).pi = root;
q.add(root);
while (!q.isEmpty()) {
int cur = q.remove();
for (int i = 0; i < 26; i++) {
int next = trie.get(cur).children[i];
if (next == -1)
continue;
if (cur == root) {
trie.get(next).pi = root;
} else {
int x = trie.get(cur).pi;
while (x != root && trie.get(x).children[i] == -1) {
x = trie.get(x).pi;
}
if (trie.get(x).children[i] != -1) {
x = trie.get(x).children[i];
}
trie.get(next).pi = x;
}
int pi = trie.get(next).pi;
trie.get(next).indexes = new ArrayList<>(trie.get(pi).indexes);
if (trie.get(next).valid != -1) {
trie.get(next).indexes.add(trie.get(next).valid);
}
q.add(next);
}
}
for (int i = 0; i < trie.size(); i++) {
System.out.print(i + " " + trie.get(i).pi);
for (int x : trie.get(i).indexes) {
System.out.print(" " + x);
}
System.out.println();
}
String s = "ABCDEABABABABCD";
int Node2 = root;
for (int i = 0; i < s.length(); i++) {
int c = s.charAt(i) - 'A';
while (Node2 != root && trie.get(Node2).children[c] == -1) {
Node2 = trie.get(Node2).pi;
}
if (trie.get(Node2).children[c] != -1) {
Node2 = trie.get(Node2).children[c];
}
for (int x : trie.get(Node2).indexes) {
System.out.println(Node2 + " " + x);
}
}
}
}