Jak sprawdzić, czy ciąg znaków zaczyna się od innego ciągu w C?

85

Czy jest coś takiego startsWith(str_a, str_b)w standardowej bibliotece C?

Powinien wziąć wskaźniki do dwóch ciągów kończących się na nullbajtach i powiedzieć mi, czy pierwszy z nich pojawia się również w całości na początku drugiego.

Przykłady:

thejh
źródło
3
Myślę, że twój trzeci przykład powinien dać prawdziwy wynik.
Michael Burr,
możliwy duplikat stackoverflow.com/questions/15515088/ ...
opuszczenie

Odpowiedzi:

76

Najwyraźniej nie ma do tego standardowej funkcji C. Więc:


Zauważ, że powyższe jest ładne i wyraźne, ale jeśli robisz to w ciasnej pętli lub pracujesz z bardzo dużymi strunami, nie oferuje najlepszej wydajności, ponieważ skanuje całą długość obu strun z przodu ( strlen). Rozwiązania takie jak wj32 lub Christoph's mogą oferować lepsze wyniki (chociaż ten komentarz o wektoryzacji jest poza moim zasięgiem C). Należy również pamiętać, rozwiązanie Fred Foo który unika strlenon str(on ma rację, że to niepotrzebne, jeśli używasz strncmpzamiast memcmp). Ma znaczenie tylko w przypadku (bardzo) dużych strun lub wielokrotnego użycia w ciasnych pętlach, ale kiedy ma to znaczenie, ma znaczenie.

T.J. Crowder
źródło
5
Powinienem wspomnieć, że zazwyczaj ciąg znaków byłby pierwszym parametrem, a przedrostek drugiego. Ale zachowałem je tak, jak powyżej, ponieważ wydawało się, że twoje pytanie zostało sformułowane ... Kolejność zależy wyłącznie od ciebie, ale naprawdę powinienem zrobić to w drugą stronę - większość funkcji łańcuchowych przyjmuje pełny ciąg jako pierwszy argument, podciąg jako drugi.
TJ Crowder
1
To eleganckie rozwiązanie, ale ma pewne problemy z wydajnością. Zoptymalizowana implementacja nigdy nie sprawdzałaby więcej niż min (strlen (pre), strlen (str)) znaków z każdego ciągu, ani też nigdy nie wyszłaby poza pierwszą niezgodność. Gdyby struny były długie, ale wczesne niedopasowania były powszechne, byłby bardzo lekki. Ale ponieważ ta implementacja zajmuje pełną długość obu ciągów z przodu, wymusza wydajność w najgorszym przypadku, nawet jeśli łańcuchy różnią się pierwszym znakiem. To, czy to naprawdę ma znaczenie, zależy od okoliczności, ale jest to potencjalny problem.
Tom Karzes,
1
@TomKarzes można zastąpić memcmpna strncmptutaj i to szybciej. Nie ma UB, ponieważ wiadomo, że oba ciągi mają co najmniej lenprebajty. strncmpsprawdza każdy bajt obu łańcuchów pod kątem wartości NUL, ale strlenwywołania już gwarantowały, że ich nie ma. (Ale nadal ma wydajność, o której wspomniałeś, kiedy prelub strjest dłuższa niż rzeczywista wspólna sekwencja początkowa.)
Jim Balter
1
@JimBalter - Bardzo dobra uwaga! Ponieważ użycie memcmppowyższego nie byłoby przywłaszczeniem z innej odpowiedzi tutaj, poszedłem dalej i zmieniłem to w odpowiedzi.
TJ Crowder
1
PS To (teraz) może być najszybsza odpowiedź na niektórych maszynach z niektórymi łańcuchami, ponieważ strleni memcmpmoże być zaimplementowana za pomocą bardzo szybkich instrukcji sprzętowych, a strlens mogą umieścić ciągi w pamięci podręcznej, unikając podwójnego trafienia w pamięć. Na takich maszynach strncmpmożna by zaimplementować jako dwa strlensi a memcmptak po prostu, ale byłoby to ryzykowne dla osoby piszącej bibliotekę, ponieważ mogłoby to zająć znacznie więcej czasu w przypadku długich ciągów z krótkimi, wspólnymi prefiksami. Tutaj to trafienie jest wyraźne, a strlenkażde z nich jest wykonywane tylko raz ( strlen+ Fred Foo strncmpzrobiłby 3).
Jim Balter
160

Nie ma do tego standardowej funkcji, ale możesz ją zdefiniować

Nie musimy się martwić, strże prebędziemy krótsi niż dlatego, że według standardu C (7.21.4.4/2):

strncmpFunkcja porównuje nie więcej niż nznaków (znaki, które następują znak NULL nie są porównywane) z tablicy wskazywanej przez s1do tablicy wskazywanej przez s2„.

Fred Foo
źródło
12
Dlaczego odpowiedź brzmi „nie”? Oczywiście odpowiedź brzmi: tak, to się nazywa strncmp.
Jasper
7
^ Powinno być oczywiste, dlaczego odpowiedź brzmi nie. Algorytm, który wykorzystuje strncmpi strlennie jest „nazywany strncmp”.
Jim Balter
34

Prawdopodobnie wybrałbym strncmp(), ale dla zabawy surowa implementacja:

Christoph
źródło
6
Podoba mi się to najbardziej - nie ma powodu, aby skanować którykolwiek ze strun na długość.
Michael Burr,
1
Prawdopodobnie wybrałbym też strlen + strncmp, ale chociaż w rzeczywistości działa, wszystkie kontrowersje wokół niejasnej definicji mnie zniechęcają. Więc wykorzystam to, dzięki.
Sam Watkins
4
Prawdopodobnie będzie to wolniejsze niż strncmp, chyba że Twój kompilator jest naprawdę dobry w wektoryzacji, ponieważ pisarze glibc z pewnością są :-)
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
Ta wersja powinna być szybsza niż wersja strlen + strncmp, jeśli przedrostek nie pasuje, zwłaszcza jeśli istnieją już różnice w pierwszych kilku znakach.
dpi
1
^ Ta optymalizacja miałaby zastosowanie tylko wtedy, gdy funkcja jest wbudowana.
Jim Balter
5

Nie jestem ekspertem w pisaniu eleganckiego kodu, ale ...

wj32
źródło
5

Użyj strstr()funkcji. Stra == strstr(stra, strb)

gscott
źródło
3
wydaje się, że jest to nieco wsteczna metoda zrobienia tego - przejdziesz przez całą ścieżkę, mimo że powinno być jasne od bardzo krótkiego początkowego segmentu, czy strb jest przedrostkiem, czy nie.
StasM
1
Przedwczesna optymalizacja jest źródłem wszelkiego zła. Myślę, że jest to najlepsze rozwiązanie, jeśli nie jest to kod krytyczny czasowo lub długie ciągi.
Frank Buss
1
@ilw To słynne powiedzenie znanych informatyków - wygoogluj to. Często jest źle stosowany (tak jak tutaj) ... patrz joshbarczak.com/blog/?p=580
Jim Balter
2

Zoptymalizowany (v.2. - poprawiony):

Zloten
źródło
2
głosowanie ujemne: startsWith("\2", "\1")zwraca 1, startsWith("\1", "\1")zwraca również 1
thejh
Ta decyzja nie użyje optymalizacji w clang, ponieważ nie używaj narzędzi.
socketpair
^ intrinsics nie pomagają tutaj, zwłaszcza jeśli ciąg docelowy jest znacznie dłuższy niż przedrostek.
Jim Balter
1

Ponieważ uruchomiłem zaakceptowaną wersję i miałem problem z bardzo długim str, musiałem dodać następującą logikę:

Jordania
źródło
1

Lub połączenie tych dwóch podejść:

EDYCJA: Poniższy kod NIE działa, ponieważ jeśli strncmp zwraca 0, nie wiadomo, czy zostało osiągnięte kończące 0 lub długość (rozmiar_bloku).

Dodatkowym pomysłem jest porównanie blokowe. Jeśli blok nie jest równy, porównaj ten blok z oryginalną funkcją:

Stałe 13, 64, 4096, a także potęgowanie z block_sizeto tylko domysły. Musiałby zostać wybrany dla użytych danych wejściowych i sprzętu.

shpc
źródło
To są dobre pomysły. Zauważ jednak, że pierwszy z nich jest technicznie niezdefiniowanym zachowaniem, jeśli prefiks jest krótszy niż 12 bajtów (13 łącznie z NUL), ponieważ standard języka nie definiuje wyniku obliczenia adresu poza łańcuchem innym niż następny bajt.
Jim Balter
@JimBalter: Czy możesz dodać odniesienie? Jeśli wskaźnik jest wyłuskiwany i znajduje się po kończącym 0, to odroczona wartość wskaźnika jest niezdefiniowana. Ale dlaczego sam adres miałby być niezdefiniowany? To tylko obliczenia.
shpc
Wystąpił jednak ogólny błąd: block_sizeinkrementacja musi nastąpić po inkrementacji wskaźnika. Teraz naprawione.
shpc