Ile różnych wspólnych podsłów mają dwa ciągi?

Na wejściu dostajemy dwa słowa, mamy powiedzieć ile różnych wspólnych podsłów mają dwa ciągine wejściu. np:
Dla:
5 9
alina
balladyna
Poprawne wyjście to:
14

Próbowałem robić algorytmy na kształt LCS, ale nie wiem w jaki sposób wykrywać i zliczać podciągi które są np dwuliterowe, mógłby mi ktoś dać jakąś podpowiedź :D

Znalazłem taką odpowiedź ale nie za bardzo ją rozumiem :(
http://www.deltami.edu.pl/temat/informatyka/2011/07/30/Neon/

Co dokładnie rozumiesz przez podsłowa, bo biorąc dowolny podciąg ze zbioru, wychodzi, że te słowa mają pięć wspólnych podsłów.

def subwords(word): 
  words = set(word[i:j] for i in range(len(word)) 
                  for j in range(i + 1, len(word) + 1))
  return words


def common_subwords(word1, word2):
  return subwords(word1).intersection(subwords(word2))



print(common_subwords("alina", "balladyna"))  # -> {'a', 'al', 'na', 'n', 'l'}

Zadanie dokładnie wygląda tak:
Neon składa się z dwóch słów. Na ile sposobów można zgasić niektóre litery w neonie, tak by litery, które pozostaną zapalone, w obu słowach układały się w ten sam niepusty podciąg? Ile różnych podciągów da się w ten sposób uzyskać?
Wejście
W pierwszym wierszu standardowego wejścia zapisano dwie liczby całkowite n,m(0 <= n, m <= 2000), długość pierwszego oraz drugiego słowa. W drugim oraz trzecim wierszu wejścia znajdują się dwa słowa z neonu,składające się z małych liter alfabetu angielskiego.
Wyjście
W pierwszym wierszu standardowego wyjścia należy wypisać ile różnych wspólnych pod słów mają dwa ciągi na wejściu. Ponieważ wynik może być bardzo duży, należy obliczyć jego resztę z dzielenia modulo 10e9+ 9.
Przykłady:

Wejście:
5 9
alina
balladyna
Wyjście:
14

Wejście:
11 9
supermarket
stokrotka
Wyjście:
17

Przepraszam że od razu nie wkleiłem tutaj całej treści zadania

Rozwiązanie naiwne, (brute force) to jako wyłączenia lampek wziąć wszystkie możliwe podzbiory obu neonów, częśc wspólna to intersection.

import itertools

def subwords(word): 
  words = [list(itertools.combinations(word, x)) for x in range(1, len(word) + 1)]
  return set(itertools.chain(*words))  # flatten words and set

def common_subwords(word1, word2):
  sub1 = subwords(word1)
  sub2 = subwords(word2)
  return len(sub1.intersection(sub2))


print(common_subwords("alina", "balladyna"))  # -> 14

Złożoność, niestety, wykładnicza.