Czy istnieje lepszy sposób zapisu metody "ciąg zawiera X"?

Właśnie patrzyłem używając Haskell i zrealizowałem (o ile mogę powiedzieć) nie ma bezpośredniego sposobu na sprawdzenie łańcucha, aby zobaczyć, czy zawiera on mniejszy ciąg. Pomyślałem więc, że po prostu spróbuję.Czy istnieje lepszy sposób zapisu metody "ciąg zawiera X"?

Zasadniczo chodziło o sprawdzenie, czy oba łańcuchy miały taki sam rozmiar i były równe. Jeśli sprawdzany łańcuch był dłuższy, rekurencyjnie odwróć głowę i ponownie uruchom sprawdzanie, dopóki sprawdzany ciąg nie będzie takiej samej długości.

Resztę możliwości wykorzystałem do dopasowania wzorców do ich obsługi. Oto, co wymyśliłem:

stringExists "" wordToCheckAgainst = False 
stringExists wordToCheckFor "" = False 
stringExists wordToCheckFor wordToCheckAgainst | length wordToCheckAgainst < length wordToCheckFor = False 
               | length wordToCheckAgainst == length wordToCheckFor = wordToCheckAgainst == wordToCheckFor 
               | take (length wordToCheckFor) wordToCheckAgainst == wordToCheckFor = True 
               | otherwise = stringExists wordToCheckFor (tail wordToCheckAgainst)

Źródło

2012-01-05 Programmin Tool

Czy sprawdziłeś numer Hoogle?

Jeśli szukasz podpisu funkcji, której szukasz (String -> String -> Bool) powinieneś zobaczyć isInfixOf wśród najlepszych wyników.

Źródło

2012-01-05 19:43:34

+1 do Hoogle. To najlepszy przyjaciel wszystkich programistów Haskell :) – Daenyth

+17

Badanie [źródła 'isInfixOf'] (http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-List.html #isInfixOf) jest pouczający. – dave4420

@ dave4420 Link jest uszkodzony. – ThreeFx

isInfixOf z Data.List pewnością rozwiąże problemu, jednak w przypadku dłuższych stogi lub perverse¹ igieł należy rozważyć bardziej zaawansowane string matching algorithms z dużo lepszej średniej i najgorszy przypadek złożoności.

¹ Rozważmy bardzo długi ciąg składający się tylko z a „S i igłę z wieloma a” s na początku i jeden b na końcu.

Źródło

2012-01-05 19:48:20 Jan

Zauważ, że jakikolwiek bardziej wydajny algorytm wymaga innej struktury danych niż' String' (lub '[a]'). –

Rzeczywiście, zazwyczaj wymagają one wstępnego przetwarzania wstępnego łańcucha wejściowego. Ich implementacja w sposób, który daje w wyniku funkcję '(String -> String -> Bool)' jest absolutnie możliwa. – Jan

Jeśli naprawdę interesuje Cię wydajność, prawdopodobnie wdrożysz go w następujący sposób: [Data.Text.Search.indices] (http://hackage.haskell.org/packages/archive/text/latest/doc/html /src/Data-Text-Search.html#indices) (uwaga: 'Data.Text.isInfixOf' jest zaimplementowana pod tym względem, z powodu lenistwa może zatrzymać się po znalezieniu pierwszego indeksu) –

Rozważ skorzystanie z funkcji text package (text na Hackage, teraz także jako część platformy Haskell) do przetwarzania tekstu. Zapewnia tekst w standardzie Unicode, który jest bardziej wydajny w czasie i miejscu niż wbudowany w listę String. Do wyszukiwania ciągów, text pakiet implements a Boyer-Moore-based algorithm, który ma lepszą złożoność niż naiwna metoda używana przez Data.List.isInfixOf.

Przykład zastosowania:

Prelude> :s -XOverloadedStrings 
Prelude> import qualified Data.Text as T 
Prelude Data.Text> T.breakOnAll "abc" "defabcged" 
[("def","abcged")] 
Prelude Data.Text> T.isInfixOf "abc" "defabcged" 
True

Źródło

2012-01-06 09:28:51

Potrzebujesz przeciążeniaString tylko w celu sprawdzenia podłańcuchów mecze to jednak dość paskudna brodawka. Alternatywa polegająca na zawijaniu w 'pack' i' unpack' jest również naprawdę niezadowalająca. – ely

Czy istnieje lepszy sposób zapisu metody "ciąg zawiera X"?

Odpowiedz

Powiązane problemy