Как проверить, начинается ли строка с другой строки в C?

85

Есть ли что-то подобное startsWith(str_a, str_b)в стандартной библиотеке Си?

Он должен принимать указатели на две строки, которые заканчиваются нулевыми байтами, и сообщать мне, появляется ли первая также полностью в начале второй.

Примеры:

thejh
источник
3
Я думаю, ваш третий пример должен дать верный результат.
Майкл Берр
возможный дубликат stackoverflow.com/questions/15515088/…
от

Ответы:

76

По-видимому, для этого нет стандартной функции C. Так:


Обратите внимание, что приведенное выше красиво и ясно, но если вы делаете это в тесном цикле или работаете с очень большими строками, это не обеспечивает наилучшей производительности, поскольку оно сканирует всю длину обеих строк впереди ( strlen). Такие решения, как wj32 или Christoph, могут предложить лучшую производительность (хотя этот комментарий о векторизации выходит за рамки моего понимания C). Также обратите внимание на решение Фреда Фу, которое избегает strlenon str(он прав, в этом нет необходимости, если вы используете strncmpвместо memcmp). Имеет значение только для (очень) больших струн или многократного использования в узких петлях, но когда это имеет значение, это имеет значение.

T.J. Краудер
источник
5
Я должен упомянуть, что обычно строка является первым параметром, а префикс - вторым. Но я оставил их, как указано выше, потому что, похоже, именно так был сформулирован ваш вопрос ... Порядок полностью зависит от вас, но я действительно должен был сделать это наоборот - большинство строковых функций принимают полную строку как первый аргумент, второй - подстрока.
TJ Crowder
1
Это элегантное решение, но у него есть некоторые проблемы с производительностью. Оптимизированная реализация никогда не будет рассматривать более min (strlen (pre), strlen (str)) символов из каждой строки и никогда не будет смотреть дальше первого несоответствия. Если бы струны были длинными, но ранние несовпадения были обычным явлением, он был бы очень легким. Но поскольку эта реализация сразу берет всю длину обеих строк, она обеспечивает наихудшую производительность, даже если строки отличаются в самом первом символе. Насколько это важно, зависит от обстоятельств, но это потенциальная проблема.
Tom Karzes 06
1
@TomKarzes Вы можете заменить memcmpна strncmpздесь , и это быстрее. UB нет, потому что известно, что обе строки содержат как минимум lenpreбайты. strncmpпроверяет каждый байт обеих строк на NUL, но strlenвызовы уже гарантировали, что их нет. (Но у него все еще есть удар по производительности, о котором вы упомянули, когда preили strдольше, чем фактическая обычная начальная последовательность.)
Джим Балтер
1
@JimBalter - Очень хорошая мысль! Поскольку использование memcmpвыше не соответствовало бы другому ответу здесь, я пошел дальше и изменил его в ответе.
TJ Crowder
1
PS Это (сейчас) может быть самым быстрым ответом на некоторых машинах с некоторыми строками, потому что strlenи memcmpможет быть реализовано с очень быстрыми аппаратными инструкциями, а strlens может помещать строки в кеш, избегая двойного попадания в память. На таких машинах strncmpможно было бы реализовать как два strlens и a, memcmpкак это, но это было бы рискованно для автора библиотеки, так как это могло бы занять гораздо больше времени для длинных строк с короткими общими префиксами. Здесь это попадание явное, и strlens выполняются только один раз каждый ( strlen+ Фред Фу strncmpсделал бы 3).
Джим Балтер
160

Для этого нет стандартной функции, но вы можете определить

Нам не нужно беспокоиться о strтом, чтобы быть короче, preпотому что согласно стандарту C (7.21.4.4/2):

strncmpФункция сравнивает не более чем nсимволы (символы , которые следуют нулевой символ не сравниваются) из массива , на который указывает s1на массив , на который указывает s2«.

Фред Фу
источник
12
Почему нет? Ясно, что да, так и называется strncmp.
Джаспер
7
^ Должно быть очевидно, почему ответ отрицательный. Алгоритм, который использует strncmpи strlenне называется strncmp.
Джим Балтер
34

Я бы, наверное, пошел strncmp(), но просто для удовольствия, сырую реализацию:

Кристоф
источник
6
Мне это нравится больше всего - нет причин сканировать любую из строк на предмет длины.
Майкл Берр
1
Я, вероятно, тоже выбрал бы strlen + strncmp, но хотя он действительно работает, все споры по поводу его расплывчатого определения меня отталкивают. Так что я воспользуюсь этим, спасибо.
Сэм Уоткинс,
4
Это, вероятно, будет медленнее, чем strncmp, если ваш компилятор действительно хорош в векторизации, потому что авторы glibc уверены :-)
Ciro Santilli 郝海东 冠状 病 六四 事件
3
Эта версия должна быть быстрее, чем версия strlen + strncmp, если префикс не совпадает, особенно если уже есть различия в первых нескольких символах.
dpi
1
^ Эта оптимизация применима только в том случае, если функция встроена.
Джим Балтер
5

Я не специалист по написанию элегантного кода, но ...

wj32
источник
5

Используйте strstr()функцию. Stra == strstr(stra, strb)

Gscott
источник
3
это кажется несколько обратным способом сделать это - вы пройдете через весь stra, даже если из очень короткого начального сегмента должно быть ясно, является ли strb префиксом или нет.
StasM
1
Преждевременная оптимизация - это корень всех зол. Я думаю, что это лучшее решение, если это не критичный по времени код или длинные строки.
Фрэнк Басс
1
@ilw Это известная поговорка известных компьютерных ученых - погуглите. Его часто неправильно применяют (как здесь) ... см. Joshbarczak.com/blog/?p=580
Джим Балтер
2

Оптимизировано (v.2. - исправлено):

Злотен
источник
2
отрицательное голосование: startsWith("\2", "\1")возвращает 1, startsWith("\1", "\1")также возвращает 1
2015
Это решение не будет использовать оптимизацию в clang, поскольку не использует instrisincs.
socketpair 08
^ intrinsics здесь не помогают, особенно если целевая строка намного длиннее префикса.
Джим Балтер
1

Поскольку я запустил принятую версию и у меня возникла проблема с очень длинной строкой, мне пришлось добавить следующую логику:

Иордания
источник
1

Или комбинация двух подходов:

РЕДАКТИРОВАТЬ: приведенный ниже код НЕ работает, потому что, если strncmp возвращает 0, неизвестно, был ли достигнут завершающий 0 или длина (block_size).

Дополнительная идея - сравнивать по блокам. Если блок не равен, сравните этот блок с исходной функцией:

Константы 13, 64, 4096, а также потенциированиеblock_size лишь догадки. Его нужно будет выбрать для используемых входных данных и оборудования.

shpc
источник
Это хорошие идеи. Однако обратите внимание, что первый - технически неопределенное поведение, если префикс короче 12 байтов (13, включая NUL), потому что стандарт языка не определяет результат вычисления адреса вне строки, кроме следующего за ним байта.
Джим Балтер
@JimBalter: Не могли бы вы добавить ссылку? Если указатель разыменован и находится после завершающего 0, то значение указателя с разыменованием не определено. Но почему сам адрес должен быть неопределенным? Это просто расчет.
shpc
Однако произошла общая ошибка: block_sizeувеличение должно происходить после увеличения указателя. Теперь исправлено.
shpc