C'è una funzione di inversione per strstr

Question

Sto cercando di trovare una funzione simile a strstr che cerca una sottostringa partendo dalla fine verso l'inizio della stringa.

Answer 1

Non credo che ci sia nella libreria lib di c, ma sarebbe banale scrivere il proprio, Ad una condizione, si conosce la lunghezza della stringa o è terminata correttamente.

Answer 2

Non ce n'è uno nella libreria C standard. Potresti riuscire a trovarne uno sul Web o potresti doverlo scrivere da solo.

Answer 3

Non so di uno. Una delle cose carine di C è che se scrivi la tua funzione, è altrettanto veloce ed efficiente di quelle della libreria. (Questo non è il caso in molte altre lingue.)

È possibile invertire la stringa e la sottostringa, quindi eseguire la ricerca.

Infine, l'altra cosa che le persone spesso fanno quando la libreria di stringhe non è abbastanza buona è quella di passare alle espressioni regolari.

Ok, ho scritto sia reverse() e rstrstr(), che potrebbe funzionare se siamo fortunati. Sbarazzarsi di __restrict per C++. Potresti anche voler creare i parametri const, ma dovrai quindi eseguire il cast del valore restituito. Per rispondere alla tua domanda di commento, puoi ottenere l'indice dall'indice della sottostringa semplicemente sottraendo il puntatore originale della stringa da esso. 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; 
} 

Answer 4

Se è possibile utilizzare C++, è possibile cercare le stringhe in questo modo:

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 

Answer 5

Per farla breve:

Nope - non v'è alcuna funzione nella libreria C che fa quello che vi serve ..

ma come altri hanno fatto notare: non è la scienza a razzo per scrivere un tale funzione ...

Answer 6

No. Questo è uno dei punti in cui la classe std :: string C++ presenta un ovvio vantaggio: insieme a std::string::find(), c'è anche std::string::rfind().

Answer 7

Here is one. test è un esercizio che lascio a voi :)

Answer 8

Una possibile, se non del tutto elegante, implementazione potrebbe sembrare:

#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; 
} 

Answer 9

C'è una funzione di libreria C trovare l'indice dell'ultima occorrenza di una sottostringa all'interno di una stringa?

Edit: As @hhafez note in un commento qui sotto, la prima soluzione che ho postato per questo era inefficiente e non corretta (perché ho avanzato il puntatore target_length, che ha funzionato bene nel mio test stupido). Puoi trovare quella versione nella cronologia delle modifiche.

Ecco un'implementazione che inizia alla fine e lavora di nuovo:

#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; 
} 

uscita:

 
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 

Answer 10

Grazie per le vostre risposte! C'è un altro modo che proviene dal forum MSDN. http://social.msdn.microsoft.com/Forums/en-US/vclanguage/thread/ed0f6ef9-8911-4879-accb-b3c778a09d94

Answer 11

Penso che si possa ancora farlo utilizzando le funzioni di libreria.

1. Utilizzare la funzione strrev per invertire la stringa.

2. Utilizzare la funzione strstr per fare tutto ciò che si vuole fare.

3. È possibile trovare l'indice di inizio (dal retro) della stringa di ricerca sottraendo l'indice iniziale della stringa di ricerca dalla lunghezza della stringa originale.

Answer 12

La libreria C standard non ha una funzione "reverse strstr", quindi è necessario cercarla o scriverla.

Mi sono inventato un paio di soluzioni e ho aggiunto del codice di test e benchmarking insieme alle altre funzioni in questo thread. Per chi è curioso, in esecuzione sul mio portatile (Ubuntu karmico, architettura amd64) l'output è simile al seguente:

$ 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 

I risultati possono essere diversi e, a seconda del compilatore e la biblioteca, l'ordinamento dei risultati può anche essere diverso.

Per ottenere l'offset (indice) della partita dall'inizio della stringa, utilizzare l'aritmetica dei puntatori:

char *match = last_strstr(haystack, needle); 
ptrdiff_t index; 
if (match != NULL) 
    index = match - haystack; 
else 
    index = -1; 

E ora, il larice (si noti che questo è puramente in C, non lo so C++ abbastanza bene per dare una risposta per esso):

/* 
* 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 (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://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; 
} 

Answer 13

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; 
} 

Answer 14

è possibile utilizzare std :: algoritmo standard find_end per questo scopo. Per esempio

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; 

Answer 15

Ecco l'impianto più semplice e semplice che potrei inventare. A differenza di altre implementazioni di questa funzione, evita la chiamata strstr iniziale che aveva altre persone come user3119703.

char * lastStrstr(const char * haystack,const char * needle){ 
    char*temp=haystack,*before=0; 
    while(temp=strstr(temp,needle)) before=temp++; 
    return before; 
} 

Answer 16

Anche se non standard, strrstr è ampiamente supportata e fa esattamente quello che vuoi.

Answer 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;  
}