SPOJ DISUBSTR

From Algorithmist
Jump to navigation Jump to search

hello every one! this problem can be solved easily by suffix array. if you are not familier with this data structure i strongly suggest you to read the folowing paper by by Manber and Myres.[1]

now consider the folowing example:
ABABA

first we construct suffix array for this string:
1 A 0
2 ABA 1
3 ABABA 3
4 BA 0
5 BABA 2

each number in third column shows the longest common prefix (LCP) of consecutive suffixes
for example LCP[5]=2 because LCP BA and BABA is BA and 2 is the length of BA


now the first question is :what is substring?
ans:any substring of string S is a prefix of some suffixes of S


now we know what we should do!!!!!!
scan the suffix array from start to end:
LCP [1]=0 //no common prefix with last element so because the length of A is one we can only construct one substring P[1]=1
LCP[2]=1 //so ignore all common cases with last suffix and count the remainder substrings: AB,ABA =3-1 ,P[2]=2 ,3 is length(SUFFIX[2]) and 1 is LCP[1]

LCP[3]=3 /// distinct substring are: ABAB ,ABABA => 5-3 ,P[3]=2
.....
.....
.....
let P[i]=length(SUFFIX[i])-LCP[i]
obviosly the sum of all P[i] will give us the number of distinct substrings of S