strstr c como funciona

strstr() para una cadena que NO termina en nulo

Question

¿Cómo hago el equivalente en lugar de strstr() para una cadena contada (es decir, no terminada en nulo) en C?

Answer 1

Acabo de encontrar esto y me gustaría compartir mi implementación. Creo que es bastante rápido y no tengo subclase.

Devuelve el índice en el pajar donde se encuentra la aguja o -1 si no se encontró.

/* binary search in memory */
int memsearch(const char *hay, int haysize, const char *needle, int needlesize) {
    int haypos, needlepos;
    haysize -= needlesize;
    for (haypos = 0; haypos <= haysize; haypos++) {
        for (needlepos = 0; needlepos < needlesize; needlepos++) {
            if (hay[haypos + needlepos] != needle[needlepos]) {
                // Next character in haystack.
                break;
            }
        }
        if (needlepos == needlesize) {
            return haypos;
        }
    }
    return -1;
}

Answer 2

Mira si la función de abajo te funciona. No lo he probado a fondo, así que te sugiero que lo hagas.

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

Si tienes miedo del comportamiento de O (m * n) (básicamente, no es necesario, tales casos no ocurren naturalmente), aquí hay una implementación de KMP que tuve alrededor y que he modificado para tomar la longitud del pajar. También una envoltura. Si desea realizar búsquedas repetidas, escriba las suyas y reutilice la matriz de borders .

No hay garantías para la falta de errores, pero parece que todavía funciona.

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 4

Utilicé este método

int memsearch(char* dataset, int datasetLength, char* target, int targetLen){
    for(int i = 0; i < datasetLength; i++){
            if(dataset[i] == target[0]){
                    int found = 1;
                    for(int j = 0; j < targetLen; j++){
                            int k = i + j;
                            if(k >= datasetLength || target[j] != dataset[k]){
                                    found = 0;
                                    break;
                            }
                    }
                    if(found) return i;
            }
    }
    return -1;
}