# 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.

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=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 =0 //no common prefix with last element so because the length of A is one we can only construct one substring P=1
LCP=1 //so ignore all common cases with last suffix and count the remainder substrings: AB,ABA =3-1 ,P=2 ,3 is length(SUFFIX) and 1 is LCP

LCP=3 /// distinct substring are: ABAB ,ABABA => 5-3 ,P=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