Definition of a tree (Taken from Wikipedia) A tree is an undirected graph \(G\) that satisfies any of the following equivalent conditions: \(G\) is connected and acyclic (contains no cycles). \(G\) is acyclic, and a simple cycle is formed if any edge is added to \(G\). \(G\) is connected, but would become disconnected if any single edge is removed from \(G\). \(G\) is connected and the 3-vertex complete graph \(K_3\) is not a minor of \(G\).

Main concept of KMP Consider the following string: \(\underbrace{a_1 a_2 a_3 a_4}_\text{text1}\)