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:
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
obviosly the sum of all P[i] will give us the number of distinct substrings of S