I didn't understand your algorithm either...What's its time complexity? My solution is consider the substrings begins at each position. For any substring, we only count the right-most occurence of it. For example in ABAB, we count ABAB and ABA when we are considering the first A, count BA and BAB for first B, count A and AB for the second A, count B for the second B and that would be 7 in total.
Now the problem is how many substrings start with the first character that does not appear later in the string, this can be solved by a procedure similar to KMP's prefix array computation (that is, we can compute in O(n) time what's the longgest prefix that also appears latter in the string) for ABAB, the longgest prefix is AB, so we just count ABA and ABAB, A and AB will be counted latter. Since for each position the counting takes O(n) time, the total running time is O(n^2) which is suitable for n=1000. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
