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:

first we construct suffix array for this string:
1 A 0
2 ABA 1
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