LCS szybciej niż O(n*m)

Czy da się uzyskać lepszą złożoność niż O(n*m) wiedząc, że oba ciągi złożone są tylko z liter 'a'..'z' (po kolei w ascii) oraz litery mogą się powtarzać (wyklucza użycie LAS)?

Wiem jak szybko policzyć gdzie znajdują się takie same znaki O(n+m), co daje mi zestaw p punktów (a1,b1) .. (ap, bp), aczkolwiek nie mam pomysłu jak to zrobić.

Wydaje mi się że jest to do zrobienia, bo O(n*m) nie przechodzi mi na spoju (http://pl.spoj.pl/problems/TLCS/ - zadanie na samą długość przechodzi), a ludzie jakoś to zaliczają.

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_optimization
Może właśnie hashe?

hashe potrafie sobie wyobrazić w użyciu gdybym zamiast liter miał całe linie, tak jak w porównywarkach plików, inaczej nie potrafię sobie wyobrazić jak miałyby mi pomóc w rozwiązaniu tego problemu.

1000x1000 daje milion co jest "rozsądną" wartością, tzn obliczenia powinny potrwać ułamek sekundy dla takiego przypadku. To, że znaki są printable nic nie zmienia, algorytm ma taką samą złożoność niezależnie od rozmiaru alfabetu.

Polecam wypróbować następujące optymalizacje:

1. Sprawdzić najdłuższy prefiks i sufiks ciągów. Jeżeli k to suma ich długości to wtedy złożoność samego LCSa wyniesie (n - k) * (m - k).
2. Wyrzucić z pierwszego ciągu znaki nie występujące w drugim i vice versa.

Nie pamiętam jaki jest status dokładnie tego problemu, ale wydaje mi się, że jest to twardy kwadratowy problem i nie da się zrobić lepiej. W zadaniu raczej chodzi o optymalizacje kwadratowego rozwiązania.

to chyba zmarnowałem popołudnie szukając lepszego rozwiązania - nawet znalazłem, ale po angielsku i napisane dość trudnym językiem (cała praca naukowa)