Pomoc z algorytmem

Cześć, usiłuję rozwiązać w Javie to zadanie: http://www.spoj.pl/problems/DICTSUB/ ale niestety ciągle dostaję TLE. Czy mógłby ktoś podpowiedzieć w jaki sposób najefektywniej sprawdzać czy dane słowo jest podciągiem drugiego, przy tych założeniach jakie tam są (czyli można usuwać literki, jednak nie wolno zamieniać ich kolejności). Oczywiście dekompresja z RLE do zwykłego słowa i potem "zwykłe" sprawdzanie (gdzie jedyną optymalizacją jest to, że jeśli w pewnym momencie mogę stwierdzić, że dane słowo nie jest podciągiem innego patrząc na ilość liter pozostałych do sprawdzenia w słowie i w szukanym podciągu) jest za wolne. Może trzeba to na jakimś drzewie robić? Patrząc na format danych wejściowych (długość słowa nawet do 10000 znaków, a w RLE max 200 znaków) wydaje mi się, że sporo liter takich samych będzie po sobie następowało czyli będą to słowa pokroju 50A70E100G itp. itd.

Dzięki z góry za pomoc.

kyrtap

Nie chce mi się programu pisać, ale wpadłem na taki pomysł (n = len(T)):

Tworzysz dla każdej litery tablicę z ilością danych liter, które wystąpiły do danego miejsca włącznie z danym miejscem (O(n)) (dla "aaaabbbba" będziesz miał tab_a = [1,2,3,4,4,4,4,4,5] i tab_b = [0,0,0,0,1,2,3,4,4]).

Następnie dla każdego słowa (które ma maksymalnie k=100 różnych kolejnych liter) znajdujesz dla każdego bloku liter odpowiedni indeks przez wyszukiwanie binarne, uwzględniając liczbę liter które były wcześniej (lower bound). Dokładniej w tym przypadku dla ciągu 3a3b1a: widzisz 3a, więc szukasz pozycji w tab_a, gdzie jest pierwsze wystąpienie 3, znajdujesz pozycję 2. Bierzesz kolejny element RLE, 3b, pobierasz wartość dla aktualnej pozycji z tablicy b, czyli tab_b[2], które jest równe 0, więc szukasz w tab_b pierwszego wystąpienia 0+3, czyli pozycji 5. Następnie widzisz 1 a. tab_a[5] == 4 więc szukasz w tab_a pozycji dla 4+1 = 5, otrzymujesz pozycję 8. Ciąg się zmieścił w tablicy, więc wypisujesz YES.

Dla każdego słowa (jest ich D) masz k wyszukiwań binarnych na tablicach o długości n, więc łączna złożoność tego kroku będzie równa O(D * k * log(n)), i całego algorytmu O(D * k * log(n) + n)

Dzięki za odpowiedź! Oczywiście rozwiązanie zaproponowane przez Ciebie wypróbuję, lecz z tego co wyczytałem ludziom algorytm przechodził dopiero przy osiągnięciu złożoności O (n log k) gdzie n - długość podciągu, k - długość wyrazu T. Niestety nic konkretnego nie znalazłem poza taką informacją (na forum SPOJ-a), więc gdyby się pojawił jeszcze jakiś pomysł to chętnie przeczytam :)

Napisałem kod bazując na Twojej wskazówce i przeszło! Dzięki Ci ogromne!