Traverse the string
for ( int i = 1 ; i < s . size ( ) ; i ++ ) { int previous_index = lps [ i - 1 ] ; while ( previous_index > 0 && s [ i ] != s [ previous_index ] ) { previous_index = lps [ previous_index - 1 ] ; }