Pomysły na znalezienie pierwszego wystąpienia z wielu

Witam,

od razu na wstępie powiem czego szukam i czego nie szukam.

Czego nie szukam:

• odpowiedzi które znajdują byle jaką implementacje która "gets the job done" - mogę ją sam napisać
• odpowiedzi z regexpami
• implementacji z pętlami
• implementacji z operacjami na kolekcjach, np array_map()

Czego szukam:

• sprytnych sposobów znalezienia jednego z wielu wystąpień, z różnymi pomysłami na to (być może jakiś hashtable albo inne cuda).
• możliwe że nie ma takiego, wtedy trudno.

No więc szukam jakiegoś sprytnego sposobu, jak w danym stringu, powiedzmy Quick brown fox jumped over a lazy dog znaleźć pierwsze wystąpienie jednego z pod-ciągów, np ['og', 'ox'] - tutaj pierwszym wystąpieniem jest ox, bo pojawia się przed og.

Pomysły?

W duchu C się zapieprzało pointerem i sprawdzało pod kątem pierwszej litery, w razie zgodności pogłębione sprawdzenie
O(n) z małym narzutem

Brzmi jak Aho-Corasick.

implementacji z pętlami ?

implementacji z pętlami

chcesz to raz sprawdzić, czy sprawdzać wiele razy?

bo jak chcesz raz sprawdzić, to raczej i tak będziesz potrzebować conajmniej jednej pętli (później można porobić jakiś indeks, ale na początku to jak sobie poradzić bez co najmniej jednej pętli?)

odpowiedzi które znajdują byle jaką implementacje która "gets the job done" - mogę ją sam napisać

no mi się nasuwają dwie implementacje tego typu, które są dość proste (ale czy muszą być jakoś wielce skomplikowane? Jaki jest twój dokładny usecase? )

Jedna "na pałę", czyli iterujemy przez znaki w stringu i sprawdzamy czy podstring zaczynający się od aktualnego znaku się zgadza z szukaną frazą:

(pseudokod)

for index in string
   for phrase in phrases
      if substring(string, index, length(phrase)) == phrase)
         return index

tylko tu mamy problem, że dla każdego znaku trzeba generować podstring (pytanie, jaki to jest rzeczywisty narzut?)

Inne rozwiązanie, jakie mi się nasuwa to iterować po znakach, ale nie sprawdzać podstringu, tylko przelatywać przez szukane frazy i sprawdzać, czy pierwszy znak się zgadza. Jeśli tak, to zinkrementować indeks znaku dla danej frazy. I przy kolejnych znakach sprawdzać czy znak równa się n-ty znak w danej frazie. Jeśli tak, to inkrementujemy (aż znajdziemy wszystkie znaki danej frazy), jeśli nie, to dla danej frazy wracamy do początku:

for character, index in string
   for phraseInfo in phraseInfos
      if phraseInfo.phrase[phraseInfo.index] == character
        phraseInfo.index += 1
        if phraseInfo.index == length(phraseInfo.phrase)
           return index // znalezione!
      else 
        phraseInfo.index = 0 // zerujemy indeks, poniewaz znaki sie nie zgadzaja
        

No np chodzi mi o to, że potrzebowałem znaleźć pozycję wystąpienia pierwszego znaku z wielu np znalezienie pozycji pierwszego znaku z ["\n", "\r", "\t", " "]. I oczywiście można by zrobić strPos() w pętli, ale ja użyłem strCSpn(), która zwraca długość najdłuższego stringa od początku który nie zawiera tych znaków. I takie jedno wywołanie funkcji wbudowanej strCSpn() mi się bardziej podoba niż pętla.

Szukam czegoś podobnego, tylko że dla całych stringów, a nie pojedynczych znaków, np ["\n", "\r\n"].

Patryk27 napisał(a):

Brzmi jak Aho-Corasick.

implementacja tego pętlami i tak jest wolniejsza niż wywołanie natywnego strPos() w pętli.

Ano, strpos() jest zapewne zaimplementowane prosto w C - ciężko to przebić;

Przypominają mi się zadania na Leetcode, gdzie to użycie gotowej funkcji z biblioteki standardowej Pythona czy innego skryptowego języka (chyba w JS też tak było) było zwykle szybsze niż implementacja tego samego w sposób algorytmiczny.