C++ strstr 是否有反向函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1634359/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is there a reverse function for strstr
提问by Manav Sharma
I am trying to find a similar function to strstrthat searches a substring starting from the end towards the beginning of the string.
我试图找到一个类似的函数来strstr搜索从字符串的末尾开始到开头的子字符串。
回答by Manav Sharma
The standard C library does not have a "reverse strstr" function, so you have to find or write your own.
标准 C 库没有“反向 strstr”函数，因此您必须自己查找或编写。
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:
我想出了几个自己的解决方案，并在该线程中添加了一些测试和基准测试代码以及其他功能。对于那些好奇的人，在我的笔记本电脑（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
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;
And now, the larch (note that this is purely in C, I do not know C++ well enough to give an answer for it):
现在，落叶松（请注意，这纯粹是用 C 语言编写的，我不太了解 C++，无法给出答案）：
#include <string.h>
#include <stdlib.h>
/* By liw. */
static char *last_strstr(const char *haystack, const char *needle)
{
if (*needle == '#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;
}
')
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 == '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
')
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 == '#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;
}
')
return((char *)s1);
ps1 = s1 + strlen(s1);
while(ps1 != s1) {
--ps1;
for (psc1 = ps1, sc2 = s2; ; )
if (*(psc1++) != *(sc2++))
break;
else if (*sc2 == '#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;
}
')
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 == '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
')
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)
{
size_t needle_length = strlen(needle);
const char* haystack_end = haystack + strlen(haystack) - needle_length;
const char* p;
size_t i;
if (*needle == '##代码##')
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;
}
回答by DigitalRoss
I don't know of one. One of the nice things about C is that if you write your own function, it's just as fast and efficient as the library ones. (This is totally not the case in many other languages.)
我不知道一个。C 的优点之一是，如果您编写自己的函数，它与库函数一样快速和高效。（在许多其他语言中完全不是这种情况。）
You could reverse the string and the substring, and then search.
您可以反转字符串和子字符串，然后进行搜索。
Finally, the other thing people often do when the string library isn't good enough is to move to regular expressions.
最后，当字符串库不够好时，人们经常做的另一件事是转向正则表达式。
Ok, I wrote both reverse()and rstrstr(), which might work if we are lucky. Get rid of __restrictfor C++. You also might want to make the parameters const, but then you will need to cast the return value. To answer your comment question, you can get the index from the address of the substring by just substracting the original string pointer from it. OK:
好的，我同时写了reverse()和rstrstr()，如果幸运的话，这可能会奏效。摆脱__restrictC++。您可能还想设置参数const，但随后您需要转换返回值。要回答您的评论问题，您只需从中减去原始字符串指针即可从子字符串的地址中获取索引。好的：
回答by jpalecek
If you can use C++, you can search strings like this:
如果你可以使用 C++，你可以像这样搜索字符串：
##代码##回答by Theo Spears
One possible, if not entirely elegant, implementation might look like:
一种可能的（如果不是完全优雅的）实现可能如下所示：
##代码##回答by Jerry Coffin
No. This is one of the places that the C++ std::string class has an obvious advantage -- along with std::string::find(), there's also std::string::rfind().
不。这是 C++ std::string 类具有明显优势的地方之一——除了std::string::find()，还有std::string::rfind().
回答by Alice
回答by Ashish
I think you can still do it using library functions.
我认为你仍然可以使用库函数来做到这一点。
1.Use strrev function to reverse the string.
1.使用strrev函数反转字符串。
2.Use strstr function to do whatever you want to do.
2.使用strstr函数做任何你想做的事。
3.You can find start index (from reverse ) of the search string by subtracting start index of the search string from the length of original string.
3.您可以通过从原始字符串的长度中减去搜索字符串的起始索引来找到搜索字符串的起始索引（反向）。
回答by Sinan ünür
Is there a C Library function to find the index to the last occurrence of a substring within a string?
是否有 C 库函数来查找字符串中子字符串最后一次出现的索引？
Edit:As @hhafez notes in a comment below, the first solution I posted for this was inefficient and incorrect (because I advanced the pointer by target_lengthwhich worked fine in my silly test). You can find that version in the edit history.
编辑：正如@hhafez 在下面的评论中指出的那样，我为此发布的第一个解决方案效率低下且不正确（因为我将指针提前，target_length在我的愚蠢测试中它运行良好）。您可以在编辑历史记录中找到该版本。
Here is an implementation that starts at the end and works back:
这是一个从最后开始并返回的实现：
##代码##Output:
输出：
##代码##回答by Manav Sharma
Thanks for your answers! There is one more way which came from the MSDN forum. http://social.msdn.microsoft.com/Forums/en-US/vclanguage/thread/ed0f6ef9-8911-4879-accb-b3c778a09d94
感谢您的回答！还有一种来自 MSDN 论坛的方法。 http://social.msdn.microsoft.com/Forums/en-US/vclanguage/thread/ed0f6ef9-8911-4879-accb-b3c778a09d94
回答by Manav Sharma
Here is one.Testing it is an exercise I'll leave to you :)
这是一个。测试它是一个练习，我会留给你:)
