ns finally contains the longest prefix which is also suffix in " pat [ 0 . . state - 1 ] c " Start from the largest possible value and stop when you find a prefix which is also suffix
for ( ns = state ; ns > 0 ; ns -- ) { if ( pat [ ns - 1 ] == x ) { for ( i = 0 ; i < ns - 1 ; i ++ ) if ( pat [ i ] != pat [ state - ns + 1 + i ] ) break ; if ( i == ns - 1 ) return ns ; } } return 0 ; }