Wie mache ich das an Ort und Stelle Äquivalent von strstr()
Für ein gezählt Zeichenfolge (z nicht nullterminiert) in C?
strstr() für einen NICHT nullterminierten String
Wenn Sie Angst vor O(m*n)-Verhalten haben – im Grunde müssen Sie das nicht, solche Fälle treten natürlich nicht auf – hier ist eine KMP-Implementierung, die ich herumliegen hatte und die ich modifiziert habe, um die Länge des Heuhaufens aufzunehmen. Auch eine Hülle. Wenn Sie wiederholt suchen möchten, schreiben Sie Ihre eigene und verwenden Sie die wieder borders
Reihe.
Keine Garantie für Fehlerfreiheit, aber es scheint immer noch zu funktionieren.
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;
}
Tim Cooper
Sehen Sie, ob die folgende Funktion für Sie funktioniert. Ich habe es nicht gründlich getestet, also würde ich vorschlagen, dass Sie dies tun.
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;
}
-
Das ist eigentlich ähnlich dem, was ich gerade benutze, aber es ist O (mn), während (ich gehe davon aus)
strstr
ist O(m + n). Also suche ich nach etwas, das nicht so lächerlich langsam ist wie meine Version. 🙂 Aber trotzdem +1, da die Idee funktioniert.– Benutzer541686
21. Dezember 2011 um 3:24 Uhr
-
@Mehrdad: Könnte sich auch lohnen, einen Blick auf diese Implementierung zu werfen: src.gnu-darwin.org/src/lib/libc/string/strnstr.c.html
– Tim Cooper
21. Dezember 2011 um 3:26 Uhr
-
Wow, da lag ich wohl falsch … also
strstr
ist typischerweise als O(mn)-Operation definiert?? Danke, dass Sie darauf hingewiesen haben … dann werde ich das wahrscheinlich gleich akzeptieren, da es der genaue Ersatz für die Frage ist.– Benutzer541686
21. Dezember 2011 um 3:27 Uhr
-
@Mehrdad: Ich habe meine Lösung ein wenig aufgeräumt, wenn Sie sie sich noch einmal ansehen möchten.
– Tim Cooper
21. Dezember 2011 um 3:32 Uhr
-
@Mehrdad C spezifiziert/definiert das O() von nicht
strstr()
.– chux – Wiedereinsetzung von Monica
5. Mai 2015 um 16:40 Uhr
Alex
Ich bin gerade darauf gestoßen und möchte meine Implementierung teilen. Es denkt es ziemlich schnell a Ich habe keine Unterrufe.
Es gibt den Index im Heuhaufen zurück, wo die Nadel gefunden wurde, oder -1, wenn sie nicht gefunden wurde.
/* 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;
}
-
Hätte weitermachen und es Boyer-Moore machen sollen, während du schon dabei warst;)
– Dyasta
27. Oktober 2016 um 20:02 Uhr
Ich habe diese Methode verwendet
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;
}
Sie müssen Ihre eigene Version schreiben.
– Seth Carnegie
21. Dezember 2011 um 3:13 Uhr
Welche Zeichenfolge ist nicht nullterminiert? Die gesuchte Zeichenfolge oder die Teilzeichenfolge?
– Tim Cooper
21. Dezember 2011 um 3:15 Uhr
@TimCooper: Der Gesuchte (Heuhaufen).
– Benutzer541686
21. Dezember 2011 um 3:16 Uhr
Sie können die Implementierung von stehlen
strnstr()
von BSD. Aber achten Sie auf diesen Fehler: mikeash.com/pyblog/dont-use-strnstr.html– Matt K
21. Dezember 2011 um 3:22 Uhr
glibc hat memmem (Nadel und Heuhaufen werden beide gezählt), ich bin sicher, dass es auch eine Public-Domain-Implementierung geben wird.
– MM
5. Mai 2015 um 13:06 Uhr