strstr() pour une chaîne qui n'est PAS null

Comment dois-je faire le en place équivalent de strstr() pour un compté chaîne (c'est à dire pas null) dans C?

Vous devrez écrire votre propre version.
Quelle chaîne de caractères n'est pas nul? La chaîne de recherche en cours, ou de la sous-chaîne de caractères?
Une recherche en cours (meule de foin).
Ce n'est pas exactement banal... je pourrais essayer de KMP ou quelque chose si j'ai vraiment besoin de le faire, mais je préfère éviter si je peux.
Vous pouvez voler de la mise en œuvre de strnstr() de BSD. Mais ce bug: mikeash.com/pyblog/dont-use-strnstr.html
Merci pour le lien, je vais jeter un oeil mais ce lien me rend un peu nerveux, haha.
Avez-vous regardé Boyer-moore chaîne de recherche? Il fonctionne très bien sans résiliation de \0s et O(4*n).
J'avais entendu parler une fois, mais je sais peu de choses sur elle et je l'avais totalement oublié, je vais regarder ça, merci!
Oui, Boyer-Moore est très bon. C'est un peu plus compliqué que KMP, donc si vous ne trouvez pas un ready-made de mise en œuvre, il peut ne pas être utile pour faire cuire vous-même. Si la performance est vraiment important, je voudrais cependant vous recommandons de BM, surtout si les aiguilles sont longues. (Dans le meilleur des cas, BM ne regarde que chaque mème caractère.)
la glibc a memmem (l'aiguille et la botte de foin à la fois pris en compte), je suis sûr qu'il y aura un domaine public de la mise en œuvre là aussi.

InformationsquelleAutor Mehrdad | 2011-12-21

c indexof null-terminated string

Si vous avez peur de O(m*n) comportement fondamentalement, vous n'avez pas besoin, de tels cas ne se produisent pas naturellement - voici une KMP mise en œuvre que j'avais couché autour de laquelle j'ai modifié pour tenir la longueur de la botte de foin. Aussi un wrapper. Si vous voulez faire des recherches répétées, écrire votre propre et la réutilisation de la borders tableau.

Pas de garanties pour le bug de l'indice d'égouttage, mais il semble encore fonctionner.

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

:O Oh wow, je vais certainement essayer cette! Merci! 🙂

InformationsquelleAutor Daniel Fischer

8

Voir si la fonction ci-dessous qui fonctionne pour vous. Je n'ai pas testé à fond, donc je vous suggère de le faire.
```
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;
}
```
- C'est en fait similaire à ce que j'utilise actuellement, mais il est O(mn), alors que (je suppose) strstr est O(m + n). Donc, je suis à la recherche de quelque chose qui n'est pas ridiculement lent comme ma version. 🙂 Mais +1 de toute façon, depuis que l'idée fonctionne.
- Peut également être la peine de prendre un coup d'oeil à cette mise en œuvre: src.gnu-darwin.org/src/lib/libc/string/strnstr.c.html
- Wow, je suppose que je me trompais, puis... donc strstr est généralement défini comme un O(mn) de l'opération?? Merci pour cette remarque... alors, je vais probablement l'accepter dans un peu, puisque c'est exactement le substitut de la question.
- J'ai nettoyé ma solution un peu, si vous voulez prendre un coup d'oeil à nouveau.
- C n'a pas de spécifier/définir les O() de strstr().
- Vous pourriez éviter la boucle de vérifier if (i + needle_length > length) par simple réduction de la length de manière appropriée de sorte que le for condition de boucle est correcte. if (needle_length > length) return NULL;, puis length -= needle_length;, et la for boucle devient for (i = 0; i <= length; i++) (changement de < à <= pour vous assurer de vérifier la dernière position). La première if vérification n'est nécessaire que parce que vous utilisez size_t; à l'aide de ssize_t permettrait d'éliminer la nécessité pour le contrôle. Bon compilateur peut être assez intelligent pour éliminer if pour vous, mais pourquoi écrire un code complexe et espérons que si vous n'avez pas besoin d'.
- Il serait également possible d'optimiser une mise en œuvre comme cela: 1) à l'Aide de memcmp pour éviter NUL vérification de strncmp. 2) à l'Aide de memchr pour trouver le premier caractère de l'aiguille dans la botte de foin, de sorte que vous ne faites pas un strncmp/memcmp appel de fonction pour chaque personnage (susceptibles de réduire le nombre d'appels par un facteur de 50x et 100x). Ou de sauter memchr et il suffit de tester le premier caractère manuellement avant d'appeler strncmp/memcmp.
InformationsquelleAutor Tim Cooper

Je viens de tomber sur ce sujet et je voudrais partager ma mise en œuvre. Il estime qu'il est assez rapide, je n'ai pas de "subcalls".

Il renvoie l'index dans la botte de foin où l'aiguille est trouvé ou -1 si il n'a pas été trouvé.

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

Devrait bien allé de l'avant et fait Boyer-Moore, tant qu'à faire 😉

InformationsquelleAutor Alex

J'ai utilisé cette méthode

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

InformationsquelleAutor Jeremiah

Vous devez vous connecter pour publier un commentaire.