Как здесь можно применить динамическое программирование?
Я работаю над проблемой http://www.spoj.pl/problems/DISUBSTR/
По заданной строке нам нужно найти общее количество ее отдельных подстрок.
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.
Я решил проблему, используя слепую реализацию массива суффиксов. Тем не менее, я хочу решить это с помощью динамического программирования. Однако я не могу придумать какой-либо подход для этой цели. Также сложность времени должна быть 0 (n * n) или быстрее. Пожалуйста, кто-нибудь может направить меня в правильном направлении Любые советы / предложения / псевдокод будут высоко оценены. Я долго об этом думал, но не могу придумать какой-либо подход DP для решения проблемы?
Решение
Я не думаю, что вы можете решить эту проблему с помощью динамического программирования, потому что нет оптимальной подструктуры. Знание ответа для части строки ничего не говорит об этой части + другой символ, например.
Проблема может быть решена путем вставки всех суффиксов строки в Trie затем считая его количество узлов. Это O(n^2) и, скорее всего, получит AC с такими короткими строками. Более эффективные методы включают использование суффиксного массива (O(n log n)) и построение дерева суффиксов в O(n),
Другие решения
Других решений пока нет …
detector