[C&++] strstr－Edison.X. Blog

以前以為 strstr 不是標準函式庫，最近才發現原來它是標準的。先放上一個範例出來

strstr 使用範例
#include <string.h>
#include <stdio.h>
 
int main()
{
    const char * str = "abcabcabaabccabcab";
    const char * pattern = "bcab";
 
    char *ret = strstr(str, pattern);
    while(ret){
        printf("find \"%s\" at position : %u\n", pattern, ret - str);
        ret = strstr(ret+1, pattern);
    }
    getchar();
    return 0;
}

輸出結果如下

find "bcab" at position : 1
find "bcab" at position : 4
find "bcab" at position : 14

幾份實作

完全不調用 string library 的作法

bf_strstr
char * bf_strstr ( const char * str1, const char * str2)
{
    char *cp = (char *) str1;
    char *s1, *s2;
 
    if ( !*str2 ) return((char *)str1);
    while (*cp)    {
        s1 = cp;
        s2 = (char *) str2;
        while ( *s1 && *s2 && (*s1==*s2) ) ++s1, ++s2;
 
        if (!*s2) return(cp);
        cp++;
    }
    return(NULL);
}

"疑似" g++ 作法，使用 strchr，再調用 strncmp

gpp_strstr
char * gpp_strstr ( const char * s1, const char * s2)
{
    register char *p = s1;
    register int len = strlen (s2);
    for (; (p = strchr (p, *s2)); p++)
        if (strncmp (p, s2, len) == 0)
            return p;
    return NULL;
}

其他 KMP 之類的演算法不適合在這篇文討論，就不放上了。

沒特殊需求不要自己重刻 string.h

strcmp、strncmp、strcpy、strncpy ，這幾個函式其實在網路上都找得到很簡單的 sample code，筆者也在另一篇 [C] C-Style string.h 部份函式實作裡給了十五份常見到的 code。

然後要強調的是，上面給的都只是網路上查得到、給初學者看、初學者用、效能很差的 code ，光是想到可以針對 aliignment 後，1 次 4 bytes 或 8 btyes 方式做寫入、取出，這技巧應該就可加速不少，這部份實作和 memcpy、memchr 很像，有興趣加速自己寫的玩具，應是先研究這兩個 library 才對，就算寫出來可能也沒比較快 ( 這種技巧真的是廣為人知，何況實作的時候可能是以組語實作) ，這裡就不再贅述。

效率？

接下來討論效率的問題。一般來講上述給的三個 (內建 strstr、純暴力、g++ 所用) 之複雜度都是 O(m * n)，而 KMP 複雜度為 O(m+n)，但不少人反應，實際上在用的時候 KMP 比 strstr 還慢 "不少" 。

雖筆者不知這些測試是怎來的，但猜測測資來源是實際資料，而不是像教科書上寫的、上面範例給的 abcaaabcaabca... 這種較特殊之字串 ( 在猜這種編碼大概只存在於基因編碼之類的吧 )，導致 pattern 在比對時才會近似於 O(m*n)。

但一般在使用搜尋文章字串時，一方面文章量並不非常大，就算文章量很大好了 ( 一本書的 pdf )，出現上述之字串機會應該不多，甚至光是「第一個字母」相同的機會就不多，KMP 發揮之空間有限 (倒是前置處理可能都是浪費時間) ；即使該字串出現機會很多，像是英文字母的 is、A 、The、This 等這種常見單字，考慮到 cache hit 問題，再考慮 KMP 調整方式，KMP 也不見得快到哪去。