# SPOJ DISUBSTR

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