NEED HELP ON (FIND STRING ROOTS)SPOJ

Правка en1, от javacoder1, 2015-12-21 11:16:22

Hi, i was trying to solve the problem http://www.spoj.com/problems/FINDSR/

This problem is the application of failure function of KMP. The function block given below (i got in one of the blogs) aims to calculate the failure function:

void table(string p){

lld length = p.size();
v[0]=0;  
v[1]=0;  
lld cur=0;
for(lld j=2;j<length;j++){
    while(cur!=0 && p[cur]!=p[j-1])
        cur=v[cur];

    if(p[cur]==p[j-1])
        cur=cur+1;

    v[j]=cur;

}

lld length_substring = length - v[length-1]-1; // i am caught in this statement

}

// v[length-1] holds the the length of the longest proper prefix which matches the longest proper suffix from [0,length-2] for example for: abcabcabcabc v[length(12)-1]=v[11]=8; which is visible in the substring (abcabcabcab) length of the longest proper prefix which matches the longest proper suffix is of length 8(abcabcab)

problem is about the intuition of calculating the length of the repeating substring lld length_substring = length — v[length-1]-1;//formula simplifies to length_substring = 12-8-1=3; which clearly is the length of(abc)

Can someone explain me the intuition behind the formula of getting the substring as well as suggest some problems on codeforces to strengthen the concepts. Thanks in advance.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский javacoder1 2015-12-21 11:16:22 1402 Initial revision (published)