Czy można zliczyć liczbę odrębnych podciągów w ciągu w O (n)?

Question

Biorąc pod ciąg s o długości n, czy można policzyć liczbę różnych podciągów w s w O (n)?

Przykład

Wejście: abb

wyjściowa: 5 ('abb', 'ab', 'bb', 'a', 'b')

Zrobiłem rozeznanie, ale nie wydaje się znaleźć algorytm, który rozwiązuje ten problem w taki skuteczny sposób. Wiem, że możliwe jest podejście O (n^2), ale czy istnieje skuteczniejszy algorytm?

Nie muszę uzyskiwać każdego z podciągów, tylko całkowitą liczbę różnych (w przypadku, gdy robi różnicę).

Answer 1

można wykorzystywać algorytm ukkonena zbudować drzewo przyrostek w czasie liniowym:

https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm

Liczba podciągi s jest następnie liczba prefiksów sznurków w trie, które można obliczyć po prostu w czasie liniowym. To tylko całkowita liczba znaków we wszystkich węzłach.

Na przykład, Twój przykład tworzy drzewo przyrostek jak:

  /\     
      b a 
      | b 
      b b 

5 znaków w drzewie, więc 5 podciągów. Każdy unikalny ciąg jest ścieżką od końca głównego po innej literze: abb, ab, a, bb, b. Liczba łańcuchów to liczba liter w drzewie.

Dokładniej:

• Każdy podciąg jest prefiksem pewnego przyrostek łańcucha;
• Wszystkie sufiksy są w trie;
• Tak więc istnieje 1-1 zależność między podciągami i ścieżkami przez trie (według definicji trie); i
• Jest 1-1 korespondencja między literami w ścieżkach drzew i niepusty, ponieważ:
  • każdy odrębny niepusty ścieżka kończy się wyraźną pozycję po jego ostatnim liście; i
  • ścieżka do pozycji następnego każdy list jest unikatowy

UWAGA dla ludzi, którzy zastanawiają się, jak to może być możliwe, aby zbudować drzewo, które zawiera O (n^2) znaki w O (N) czas:

Istnieje trik do reprezentacji drzewa sufiksu. Zamiast zapisywać rzeczywiste ciągi w węzłach drzewa, po prostu przechowujesz wskaźniki w orignal string, więc węzeł zawierający "abb" nie ma "abb", ma (0,3) - 2 liczby całkowite na węzeł, bez względu na to, jak długo łańcuch w każdym węźle jest, a drzewo przyrostków ma węzły O (N).

Answer 2

Skonstruuj LCP array i odejmij jego sumę od liczby podciągów (n (n + 1)/2).