Implementation：Sunday 字符串匹配

int sunday(string str, string pattern) {
    int str_len = str.length();
    int pat_len = pattern.length();
    
    int char_pos[256];
    for (int i = 0; i<256; i++) char_pos[i] = -1;
    
    for (int i = pat_len - 1; i>=0; i--) char_pos[pattern[i]] = i;
    
    int i = 0;
    int j = 0;
    
    while (i + pat_len <= str_len) {
        while (j < pat_len && str[i] == pattern[j]) {
            i++, j++;
        }
        if (j == pat_len) return i - pat_len;

        int k = i + pat_len - j;
        int p = 0;
        
        while ( k < str_len && (p = char_pos[str[k]]) == -1) {
            k += pat_len;
        }
        
        i = k - p;
        j = 0;
    }
    return -1;
}

比KMP好理解多了

参考：

http://www.cnblogs.com/lbsong/archive/2012/05/25/2518188.html

简化：

 1 int sunday(const char* pattern, const char* str) {
 2     if (pattern == NULL || str == NULL) {
 3         return -1;
 4     }
 5     int slen = 0, plen = 0;
 6 
 7     while (pattern[plen] != '') plen++;
 8     while (str[slen] != '') slen++;
 9     
10     int tbl[128];
11     for (int i=0; i<128; i++) tbl[i] = -1;
12     for (int i=0; i<plen; i++) tbl[pattern[i]] = i;
13     
14     int pi = 0, si = 0;
15     
16     while (si < slen) {
17         while (str[si] == pattern[pi] && si < slen) si++, pi++;
18         if (pi == plen) return si - plen;
19         int nidx = plen - pi + si;
20         int offset = tbl[str[nidx]];
21         si = nidx - offset;
22         pi = 0;
23     }
24     return -1;
25 }