是否有一个的strstr反转功能
问题描述：
我试图找到一个类似的功能，以的strstr ，搜索子串从对字符串的开头结尾开始。
I am trying to find a similar function to strstr that searches a substring starting from the end towards the beginning of the string.
答
标准C库没有反向的strstr的功能，所以你必须找到或编写自己的。
The standard C library does not have a "reverse strstr" function, so you have to find or write your own.
我想出了几个我自己的解决方案，并在该线程中的其它功能一起加入了一些测试和基准测试code。对于那些好奇，我的笔记本电脑（Ubuntu的业力，AMD64架构）上运行的输出是这样的：
I came up with a couple of solutions of my own, and added some testing and benchmarking code together with the other functions in this thread. For those curious, running on my laptop (Ubuntu karmic, amd64 architecture) the output looks like this:
$ 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
您的结果可能会有所不同，并根据您的编译器和库，结果的排序也可能不同。
Your results may be different and, depending on your compiler and library, the ordering of the results may also be different.
要在字符串的开头拿到赛的偏移量（指数），使用指针运算：
To get the offset (index) of the match from the beginning of the string, use pointer arithmetic:
char *match = last_strstr(haystack, needle);
ptrdiff_t index;
if (match != NULL)
index = match - haystack;
else
index = -1;
而现在，落叶松（注意，这纯粹是C，我不知道C ++不够好，给它一个答案）：
And now, the larch (note that this is purely in C, I do not know C++ well enough to give an answer for it):
/*
* In response to
* http://*.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 (liw@liw.fi) 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://*.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://*.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://*.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;
}