strstr() एक स्ट्रिंग के लिए है कि रिक्त-समाप्त नहीं है

Question

मैं यथा-स्थान एक के लिए strstr() के बराबर सी में स्ट्रिंग (अर्थात नहीं अशक्त-समाप्त) की गिनती कैसे करते हैं?

Answer 1

आप हे (एम * एन) व्यवहार से डर रहे हैं - मूल रूप से, आप की जरूरत नहीं है, इस तरह के मामलों को स्वाभाविक रूप से नहीं होती है - यहाँ एक KMP कार्यान्वयन मैं झूठ बोल रहा था जो चारों ओर मैं करने के लिए संशोधित किया है घास की लंबाई ले लो। एक रैपर भी। यदि आप बार-बार खोज करना चाहते हैं, तो अपना खुद का लिखें और borders सरणी का पुन: उपयोग करें।

बग-फरीनेस के लिए कोई गारंटी नहीं है, लेकिन ऐसा लगता है कि यह अभी भी काम करता है।

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

देखें कि नीचे दिया गया कार्य आपके लिए काम करता है या नहीं। मैंने इसे पूरी तरह से परीक्षण नहीं किया है, इसलिए मैं सुझाव दूंगा कि आप ऐसा करते हैं।

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

मैं बस इस पर आया और मैं अपना कार्यान्वयन साझा करना चाहता हूं। यह बहुत तेज़ लगता है कि मेरे पास कोई सबकॉल नहीं है।

यह इंडेक्स को घास के मैदान में लौटाता है जहां सुई मिलती है या -1 अगर यह नहीं मिला।

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