hiukim's blog

By hiukim, 8 years ago, In English

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?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!