strstr() una stringa che non è terminazione Null

Question

Come faccio il sul posto equivalente di strstr() per un contato stringa (cioè non terminazione null) in C?

Answer 1

Se avete paura di O (m * n) il comportamento - in fondo, non è necessario, tali casi non si verificano in natura - ecco un'implementazione KMP che avevo in giro che ho modificato per prendi la lunghezza del pagliaio. Anche un involucro. Se si desidera effettuare ricerche ripetute, scrivere le proprie e riutilizzare l'array borders.

Nessuna garanzia di bug-freeness, ma sembra che funzioni ancora.

int *kmp_borders(char *needle, size_t nlen){ 
    if (!needle) return NULL; 
    int i, j, *borders = malloc((nlen+1)*sizeof(*borders)); 
    if (!borders) return NULL; 
    i = 0; 
    j = -1; 
    borders[i] = j; 
    while((size_t)i < nlen){ 
     while(j >= 0 && needle[i] != needle[j]){ 
      j = borders[j]; 
     } 
     ++i; 
     ++j; 
     borders[i] = j; 
    } 
    return borders; 
} 

char *kmp_search(char *haystack, size_t haylen, char *needle, size_t nlen, int *borders){ 
    size_t max_index = haylen-nlen, i = 0, j = 0; 
    while(i <= max_index){ 
     while(j < nlen && *haystack && needle[j] == *haystack){ 
      ++j; 
      ++haystack; 
     } 
     if (j == nlen){ 
      return haystack-nlen; 
     } 
     if (!(*haystack)){ 
      return NULL; 
     } 
     if (j == 0){ 
      ++haystack; 
      ++i; 
     } else { 
      do{ 
       i += j - (size_t)borders[j]; 
       j = borders[j]; 
      }while(j > 0 && needle[j] != *haystack); 
     } 
    } 
    return NULL; 
} 

char *sstrnstr(char *haystack, char *needle, size_t haylen){ 
    if (!haystack || !needle){ 
     return NULL; 
    } 
    size_t nlen = strlen(needle); 
    if (haylen < nlen){ 
     return NULL; 
    } 
    int *borders = kmp_borders(needle, nlen); 
    if (!borders){ 
     return NULL; 
    } 
    char *match = kmp_search(haystack, haylen, needle, nlen, borders); 
    free(borders); 
    return match; 
} 

Answer 2

Verificare se la funzione seguente funziona correttamente. Non l'ho testato a fondo, quindi ti suggerisco di farlo.

char *sstrstr(char *haystack, char *needle, size_t length) 
{ 
    size_t needle_length = strlen(needle); 
    size_t i; 

    for (i = 0; i < length; i++) 
    { 
     if (i + needle_length > length) 
     { 
      return NULL; 
     } 

     if (strncmp(&haystack[i], needle, needle_length) == 0) 
     { 
      return &haystack[i]; 
     } 
    } 
    return NULL; 
} 

Answer 3

Mi sono appena imbattuto in questo e mi piacerebbe condividere la mia implementazione. Penso che sia abbastanza veloce a non ho alcun sottolivello.

Restituisce l'indice nel pagliaio dove viene trovato l'ago o -1 se non è stato trovato.