Я пытаюсь найти аналогичную функцию для strstr, которая ищет подстроку, начиная с конца в начале строки.
Есть ли обратная функция для strstr
Ответ 1
Я не знаю одного. Одна из приятных вещей в C заключается в том, что если вы пишете свою собственную функцию, она будет столь же быстрой и эффективной, как и библиотеки. (Это совсем не так на многих других языках.)
Вы можете изменить строку и подстроку, а затем выполнить поиск.
Наконец, другое, что люди часто делают, когда строковая библиотека недостаточно хороша, - это перемещение в регулярные выражения.
Хорошо, я написал оба reverse() и rstrstr(), которые могут работать, если нам повезет. Избавьтесь от __restrict для С++. Вы также можете захотеть сделать параметры const, но тогда вам нужно будет указать возвращаемое значение. Чтобы ответить на ваш вопрос, вы можете получить индекс с адреса подстроки, просто вычеркнув из него исходный указатель строки. OK:
#include <stdlib.h>
#include <string.h>
char *reverse(const char * __restrict const s)
{
if (s == NULL)
return NULL;
size_t i, len = strlen(s);
char *r = malloc(len + 1);
for(i = 0; i < len; ++i)
r[i] = s[len - i - 1];
r[len] = 0;
return r;
}
char *rstrstr(char *__restrict s1, char *__restrict s2)
{
size_t s1len = strlen(s1);
size_t s2len = strlen(s2);
char *s;
if (s2len > s1len)
return NULL;
for (s = s1 + s1len - s2len; s >= s1; --s)
if (strncmp(s, s2, s2len) == 0)
return s;
return NULL;
}
Ответ 2
Стандартная библиотека C не имеет функции "обратного strstr", поэтому вам нужно найти или написать свой собственный.
Я придумал пару собственных решений и добавил некоторые тесты и сравнительный код вместе с другими функциями в этом потоке. Для любопытных, работающих на моем ноутбуке (Ubuntu karmic, amd64), результат выглядит следующим образом:
$ gcc -O2 --std=c99 strrstr.c && ./a.out
#1 0.123 us last_strstr
#2 0.440 us theo
#3 0.460 us cordelia
#4 1.690 us digitalross
#5 7.700 us backwards_memcmp
#6 8.600 us sinan
Ваши результаты могут быть разными и, в зависимости от вашего компилятора и библиотеки, упорядочение результатов также может быть различным.
Чтобы получить смещение (индекс) совпадения от начала строки, используйте арифметику указателя:
char *match = last_strstr(haystack, needle);
ptrdiff_t index;
if (match != NULL)
index = match - haystack;
else
index = -1;
И теперь, лиственница (обратите внимание, что это чисто в C, я не знаю С++ достаточно хорошо, чтобы дать ответ для нее):
/*
* In response to
* http://stackoverflow.com/questions/1634359/is-there-a-reverse-fn-for-strstr
*
* Basically, strstr but return last occurence, not first.
*
* This file contains several implementations and a harness to test and
* benchmark them.
*
* Some of the implementations of the actual function are copied from
* elsewhere; they are commented with the location. The rest of the coe
* was written by Lars Wirzenius ([email protected]) and is hereby released into
* the public domain. No warranty. If it turns out to be broken, you get
* to keep the pieces.
*/
#include <string.h>
#include <stdlib.h>
/* By liw. */
static char *last_strstr(const char *haystack, const char *needle)
{
if (*needle == '\0')
return (char *) haystack;
char *result = NULL;
for (;;) {
char *p = strstr(haystack, needle);
if (p == NULL)
break;
result = p;
haystack = p + 1;
}
return result;
}
/* By liw. */
static char *backwards_memcmp(const char *haystack, const char *needle)
{
size_t haylen = strlen(haystack);
if (*needle == '\0')
return (char *) haystack;
size_t needlelen = strlen(needle);
if (needlelen > haylen)
return NULL;
const char *p = haystack + haylen - needlelen;
for (;;) {
if (memcmp(p, needle, needlelen) == 0)
return (char *) p;
if (p == haystack)
return NULL;
--p;
}
}
/* From http://stuff.mit.edu/afs/sipb/user/cordelia/Diplomacy/mapit/strrstr.c
*/
static char *cordelia(const char *s1, const char *s2)
{
const char *sc1, *sc2, *psc1, *ps1;
if (*s2 == '\0')
return((char *)s1);
ps1 = s1 + strlen(s1);
while(ps1 != s1) {
--ps1;
for (psc1 = ps1, sc2 = s2; ; )
if (*(psc1++) != *(sc2++))
break;
else if (*sc2 == '\0')
return ((char *)ps1);
}
return ((char *)NULL);
}
/* From http://stackoverflow.com/questions/1634359/
is-there-a-reverse-fn-for-strstr/1634398#1634398 (DigitalRoss). */
static char *reverse(const char *s)
{
if (s == NULL)
return NULL;
size_t i, len = strlen(s);
char *r = malloc(len + 1);
for(i = 0; i < len; ++i)
r[i] = s[len - i - 1];
r[len] = 0;
return r;
}
char *digitalross(const char *s1, const char *s2)
{
size_t s1len = strlen(s1);
size_t s2len = strlen(s2);
const char *s;
if (s2len == 0)
return (char *) s1;
if (s2len > s1len)
return NULL;
for (s = s1 + s1len - s2len; s >= s1; --s)
if (strncmp(s, s2, s2len) == 0)
return (char *) s;
return NULL;
}
/* From http://stackoverflow.com/questions/1634359/
is-there-a-reverse-fn-for-strstr/1634487#1634487 (Sinan Ünür). */
char *sinan(const char *source, const char *target)
{
const char *current;
const char *found = NULL;
if (*target == '\0')
return (char *) source;
size_t target_length = strlen(target);
current = source + strlen(source) - target_length;
while ( current >= source ) {
if ( (found = strstr(current, target)) ) {
break;
}
current -= 1;
}
return (char *) found;
}
/* From http://stackoverflow.com/questions/1634359/
is-there-a-reverse-fn-for-strstr/1634441#1634441 (Theo Spears). */
char *theo(const char* haystack, const char* needle)
{
int needle_length = strlen(needle);
const char* haystack_end = haystack + strlen(haystack) - needle_length;
const char* p;
size_t i;
if (*needle == '\0')
return (char *) haystack;
for(p = haystack_end; p >= haystack; --p)
{
for(i = 0; i < needle_length; ++i) {
if(p[i] != needle[i])
goto next;
}
return (char *) p;
next:;
}
return 0;
}
/*
* The rest of this code is a test and timing harness for the various
* implementations above.
*/
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Check that the given function works. */
static bool works(const char *name, char *(*func)(const char *, const char *))
{
struct {
const char *haystack;
const char *needle;
int offset;
} tests[] = {
{ "", "", 0 },
{ "", "x", -1 },
{ "x", "", 0 },
{ "x", "x", 0 },
{ "xy", "x", 0 },
{ "xy", "y", 1 },
{ "xyx", "x", 2 },
{ "xyx", "y", 1 },
{ "xyx", "z", -1 },
{ "xyx", "", 0 },
};
const int num_tests = sizeof(tests) / sizeof(tests[0]);
bool ok = true;
for (int i = 0; i < num_tests; ++i) {
int offset;
char *p = func(tests[i].haystack, tests[i].needle);
if (p == NULL)
offset = -1;
else
offset = p - tests[i].haystack;
if (offset != tests[i].offset) {
fprintf(stderr, "FAIL %s, test %d: returned %d, haystack = '%s', "
"needle = '%s', correct return %d\n",
name, i, offset, tests[i].haystack, tests[i].needle,
tests[i].offset);
ok = false;
}
}
return ok;
}
/* Dummy function for calibrating the measurement loop. */
static char *dummy(const char *haystack, const char *needle)
{
return NULL;
}
/* Measure how long it will take to call the given function with the
given arguments the given number of times. Return clock ticks. */
static clock_t repeat(char *(*func)(const char *, const char *),
const char *haystack, const char *needle,
long num_times)
{
clock_t start, end;
start = clock();
for (long i = 0; i < num_times; ++i) {
func(haystack, needle);
}
end = clock();
return end - start;
}
static clock_t min(clock_t a, clock_t b)
{
if (a < b)
return a;
else
return b;
}
/* Measure the time to execute one call of a function, and return the
number of CPU clock ticks (see clock(3)). */
static double timeit(char *(*func)(const char *, const char *))
{
/* The arguments for the functions to be measured. We deliberately
choose a case where the haystack is large and the needle is in
the middle, rather than at either end. Obviously, any test data
will favor some implementations over others. This is the weakest
part of the benchmark. */
const char haystack[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"b"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
const char needle[] = "b";
/* First we find out how many repeats we need to do to get a sufficiently
long measurement time. These functions are so fast that measuring
only a small number of repeats will give wrong results. However,
we don't want to do a ridiculously long measurement, either, so
start with one repeat and multiply it by 10 until the total time is
about 0.2 seconds.
Finally, we measure the dummy function the same number of times
to get rid of the call overhead.
*/
clock_t mintime = 0.2 * CLOCKS_PER_SEC;
clock_t clocks;
long repeats = 1;
for (;;) {
clocks = repeat(func, haystack, needle, repeats);
if (clocks >= mintime)
break;
repeats *= 10;
}
clocks = min(clocks, repeat(func, haystack, needle, repeats));
clocks = min(clocks, repeat(func, haystack, needle, repeats));
clock_t dummy_clocks;
dummy_clocks = repeat(dummy, haystack, needle, repeats);
dummy_clocks = min(dummy_clocks, repeat(dummy, haystack, needle, repeats));
dummy_clocks = min(dummy_clocks, repeat(dummy, haystack, needle, repeats));
return (double) (clocks - dummy_clocks) / repeats / CLOCKS_PER_SEC;
}
/* Array of all functions. */
struct func {
const char *name;
char *(*func)(const char *, const char *);
double secs;
} funcs[] = {
#define X(func) { #func, func, 0 }
X(last_strstr),
X(backwards_memcmp),
X(cordelia),
X(digitalross),
X(sinan),
X(theo),
#undef X
};
const int num_funcs = sizeof(funcs) / sizeof(funcs[0]);
/* Comparison function for qsort, comparing timings. */
int funcmp(const void *a, const void *b)
{
const struct func *aa = a;
const struct func *bb = b;
if (aa->secs < bb->secs)
return -1;
else if (aa->secs > bb->secs)
return 1;
else
return 0;
}
int main(void)
{
bool ok = true;
for (int i = 0; i < num_funcs; ++i) {
if (!works(funcs[i].name, funcs[i].func)) {
fprintf(stderr, "%s does not work\n", funcs[i].name);
ok = false;
}
}
if (!ok)
return EXIT_FAILURE;
for (int i = 0; i < num_funcs; ++i)
funcs[i].secs = timeit(funcs[i].func);
qsort(funcs, num_funcs, sizeof(funcs[0]), funcmp);
for (int i = 0; i < num_funcs; ++i)
printf("#%d %.3f us %s\n", i+1, funcs[i].secs * 1e6, funcs[i].name);
return 0;
}
Ответ 3
Если вы можете использовать С++, вы можете искать строки следующим образом:
std::string::iterator found=std::search(haystack.rbegin(), haystack.rend(), needle.rbegin(), needle.rend()).base();
// => yields haystack.begin() if not found, otherwise, an iterator past-the end of the occurence of needle
Ответ 4
Одна возможная, если не совсем элегантная, реализация может выглядеть так:
#include "string.h"
const char* rstrstr(const char* haystack, const char* needle)
{
int needle_length = strlen(needle);
const char* haystack_end = haystack + strlen(haystack) - needle_length;
const char* p;
size_t i;
for(p = haystack_end; p >= haystack; --p)
{
for(i = 0; i < needle_length; ++i) {
if(p[i] != needle[i])
goto next;
}
return p;
next:;
}
return 0;
}
Ответ 5
Нет. Это одно из мест, в которых класс С++ std::string имеет очевидное преимущество - вместе с std::string::find() также есть std::string::rfind().
Ответ 6
Есть ли функция C Library, чтобы найти индекс для последнего вхождения подстроки в строке?
Изменить: Как отмечает @hhafez в комментарии ниже, первое решение, которое я разместил для этого, было неэффективным и неправильным (потому что я переместил указатель на target_length, который отлично работал в моем глупом тесте), Вы можете найти эту версию в истории редактирования.
Вот реализация, которая начинается в конце и работает:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const char *
findlast(const char *source, const char *target) {
const char *current;
const char *found = NULL;
size_t target_length = strlen(target);
current = source + strlen(source) - target_length;
while ( current >= source ) {
if ( (found = strstr(current, target)) ) {
break;
}
current -= 1;
}
return found;
}
int main(int argc, char *argv[]) {
if ( argc != 3 ) {
fputs("invoke with source and search strings as arguments", stderr);
return EXIT_FAILURE;
}
const char *found = findlast(argv[1], argv[2]);
if ( found ) {
printf("Last occurence of '%s' in '%s' is at offset %d\n",
argv[2], argv[1], found - argv[1]
);
}
return 0;
}
Вывод:
C:\Temp> st "this is a test string that tests this" test Last occurence of 'test' in 'this is a test string that tests this' is at offset 27
Ответ 7
Я думаю, вы все еще можете это сделать, используя библиотечные функции.
1. Используйте функцию strrev для изменения строки.
2. Используйте функцию strstr для выполнения того, что вы хотите сделать.
3.Вы можете найти начальный индекс (от обратного) строки поиска, вычитая начальный индекс строки поиска из длины исходной строки.
Ответ 8
Хотя нестандартное, strrstr широко поддерживается и делает именно то, что вы хотите.
Ответ 9
Я не верю, что есть в c строке lib, но было бы тривиально писать ваши собственные. При одном условии вы знаете длину строки или ее правильное завершение.
Ответ 10
В стандартной библиотеке C нет ни одного. Возможно, вы сможете найти его в Интернете, или вам, возможно, придется написать свой собственный.
Ответ 11
Короче говоря:
Нет - в C-библиотеке нет функции, которая делает то, что вам нужно.
Но, как указывали другие, это не ракетостроение, чтобы написать такую функцию...
Ответ 12
Вот он. Тестирование - это упражнение, которое я вам оставлю:)
Ответ 13
Спасибо за ваши ответы! Есть еще один способ, который пришел с форума MSDN. http://social.msdn.microsoft.com/Forums/en-US/vclanguage/thread/ed0f6ef9-8911-4879-accb-b3c778a09d94
Ответ 14
char * strrstr(char *_Str, char *_SubStr){
char *returnPointer, *p;
//find 1st occurence. if not found, return NULL
if ( (p=strstr(_Str, _SubStr))==NULL)
return NULL;
//loop around until no more occurences
do{
returnPointer=p;
++p;
}while(p=strstr(p, _SubStr));
return returnPointer;
}
Ответ 15
Для этой цели вы можете использовать стандартный алгоритм std:: find_end. Например
char s[] = "What is the last word last";
char t[] = "last";
std::cout << std::find_end( s, s + sizeof( s ) - 1, t, t + sizeof( t ) -1 )
<< std::endl;
Ответ 16
Вот самая минимальная простая имплантация, которую я мог бы придумать. В отличие от других реализаций этой функции, он избегает начального вызова strstr, который был у некоторых других пользователей, таких как user3119703.
char * lastStrstr(const char * haystack,const char * needle){
char*temp=haystack,*before=0;
while(temp=strstr(temp,needle)) before=temp++;
return before;
}
Ответ 17
char* strrstr(char * _Str, const char * _SubStr)
{
const BYTE EQUAL=0;
int i=0, src_len = strlen(_Str), find_len = strlen(_SubStr),
tail_count=0;
for(i=src_len; i>-1; i--)
{
if(_Str[i] == _SubStr[0] && tail_count >= find_len)
{
if(strncmp(&_Str[i], _SubStr, find_len) == EQUAL)
{
return &_Str[i];
}
}
tail_count++;
}
return NULL;
}