So I'm studying the failure function from this topcoder tutorial: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching

and it said "given a string (a quite long one), find all its proper suffixes that are also prefixes of it. All we have to do is just to calculate the "failure function" of the given string and using the information stored in it to print the answer."

I couldn't figure out how I can do that with the failure function. Can anyone give some ideas?

Suppose u are searching for pattern

`P=abac`

in text`T=ababac`

. let`i`

be the index moving through`P`

and`j`

be the index moving through`T`

and they both start from`0`

.So,

`P[0]=T[0] increment both i and j by 1. i=1, j=1`

`P[1]=T[1] increment both i and j by 1. i=2, j=2`

`P[3] not equals T[3]`

, but lets see what information we have got with us, we know that we have seen`aba`

which means we have seen the suffixes of`aba`

as well`ba`

and`a`

. Out of which`ba`

is not a prefix of P so it is of no use but turns out`a`

is a prefix of P so from now on we will try to extend pattern from index`1`

,`i=1,j=3`

(This is exactly what the failure function stores!)`P[1]=T[3](bingo!) increment both i and j. i=2, j=4`

Similarly,

`P[2]=T[4].`

`P[3]=T[5].`

Match found!