CODEWITHSUNDEEP
c++algorithmlogicdynamic-programming
user1724072
user1724072

Reputation: 331

How can dynamic programming be applied here?

I am working on the problem http://www.spoj.pl/problems/DISUBSTR/ Given a string, we need to find the total number of its distinct substrings.

Input

T- number of test cases. T<=20;
Each test case consists of one string, whose length is <= 1000

Output

For each test case output one number saying the number of distinct substrings.

Example

Sample Input:
2
CCCCC
ABABA

Sample Output:
5
9

    Explanation for the testcase with string ABABA: 
    len=1 : A,B
    len=2 : AB,BA
    len=3 : ABA,BAB
    len=4 : ABAB,BABA
    len=5 : ABABA
    Thus, total number of distinct substrings is 9.

I have solved the problem using blind implementation of suffix array . However,I want to solve it using Dynamic Programming.However I am not able to think of any approach for the purpose.Also the time complexity needs to be 0(n*n) or faster.Please can anyone guide me in the right direction.Any hints/suggestions/pseudo code will be highly appreciated.I have been thinking on it for a long time but can't think of any DP approach to solve the problem?

Upvotes: 2

Views: 471

Answers (1)

IVlad
IVlad

Reputation: 43507

I don't think you can solve this using dynamic programming, because there is no optimal substructure. Knowing the answer for a part of the string does not tell you anything about that part + another character for example.

The problem can be solved by inserting all suffixes of the string in a trie then counting its number of nodes. This is O(n^2) and will most likely get AC with such short strings. More efficient methods involve using a suffix array (O(n log n)) and building a suffix tree in O(n).

Upvotes: 2

Related Questions