W programie muszę efektywnie odpowiadać na zapytania w następującej formie:

Podano zestaw ciągówA i ciąg zapytaniaq wróć wszystkos ∈ A taki, że q jest apodsekwencja zs

Na przykład podaneA = {"abcdef", "aaaaaa", "ddca"} iq = "acd" dokładnie"abcdef" powinien zostać zwrócony.

Oto, co uważałem do tej pory:

Dla każdego możliwego znaku utwórz posortowaną listę wszystkich ciągów / lokalizacji, w których się pojawia. W przypadku zapytań przeplataj listy zaangażowanych znaków i skanuj je, szukając dopasowań w granicach łańcucha.

Prawdopodobnie byłoby to bardziej efektywne w przypadku słów niż znaków, ponieważ ograniczona liczba różnych znaków sprawi, że listy powrotu będą bardzo gęste.

Dla każdego przedrostka nq może mieć, zapisz listę wszystkich pasujących ciągów.n może być realistycznie zbliżony do 3. W przypadku ciągów zapytań dłuższych niż brute wymuszamy początkową listę.

Może to trochę przyspieszyć, ale można łatwo wyobrazić sobie, że niektóre n-podsekwencje są obecne w pobliżu wszystkich łańcuchówA, co oznacza, że ​​najgorszy przypadek jest taki sam jak brutalny wymuszanie całego zestawu.

Czy znasz jakieś struktury danych, algorytmy lub triki przetwarzania wstępnego, które mogą być pomocne w skutecznym wykonaniu powyższego zadania dla dużychAs? (Mójss będzie około 100 znaków)

Aktualizacja: Niektórzy sugerują użycie LCS do sprawdzenia, czyq jest podciągiems. Chcę tylko przypomnieć, że można to zrobić za pomocą prostej funkcji, takiej jak:

def isSub(q,s):
  i, j = 0, 0
  while i != len(q) and j != len(s):
    if q[i] == s[j]:
      i += 1
      j += 1
    else:
      j += 1
  return i == len(q)

Aktualizacja 2: Poproszono mnie o podanie bardziej szczegółowych informacji na temat naturyq, A i jego elementy. Chociaż wolę coś, co działa tak ogólnie, jak to możliwe, zakładamA będzie miał długość około 10 ^ 6 i będzie musiał obsługiwać wstawianie. Elementys będzie krótszy o średniej długości 64. Zapytaniaq będzie mieć od 1 do 20 znaków i będzie używany do wyszukiwania na żywo, więc zapytanie „ab” zostanie wysłane tuż przed zapytaniem „abc”. Ponownie, wolałbym, aby rozwiązanie wykorzystywało powyższe w jak najmniejszym stopniu.

Aktualizacja 3: Przyszło mi do głowy, że struktura danych zO(n^{1-epsilon}) wyszukiwania, pozwoli ci rozwiązać OVP / obalić hipotezę SETH. To jest prawdopodobnie przyczyną naszego cierpienia. Jedyne opcje to obalenie hipotezy, zastosowanie przybliżenia lub skorzystanie z zestawu danych. Wyobrażam sobie quadlety i próby zrobią ostatnie w różnych ustawieniach.