学点字符串匹配——shiftAnd/shiftOr

　　这个算法利用了位运算的优势速度很快，易于实现，缺点是模式串不能太长。据说在适用范围内速度是kmp的至少2倍。算法思想是用一个数字prefix的二进制去表示模式串的前缀，prefix的二进制第i位表示模式串的前缀0～i。如果这个前缀i是当前搜索到的匹配串的后缀时，将第i位至1。算法就是从匹配串的第0个字符到最后一个字符不断更新prefix的值每次更新后看最长的前缀（即模式串）的位是否被至1，如果是说明得到了一个匹配。

　　下面说明下更新的过程。假如求出了比较匹配串第j位时的prefix，现在求比较j+1位的情况：prefix第i位为1当且仅当prefix第i-1位为1（匹配了i-1个字符），并且第i位所在字符和匹配串第j+1个字符相等。按下面实现来说，每次循环将prefix左移一位，第0位至一，在&上一个代表第i个字符是否匹配模式串某位的数字（这个通过初始化得到），就得到更新后的prefix。

　　shiftAnd和shiftOr的思想一致。只是实现时存的是反码，因为prefix左移自然引入第0位的是0，为了减去或运算，才引入反码表示。

上代码～

 1 //return a hashtable 代表字母表中的各个元素是否能成为模式串的后缀，用64位位压缩表示
 2 long long * initAlphbat(char *patternString)
 3 {
 4     long long *hash = (long long *) malloc(256 * sizeof(long long));
 5     unsigned int idx = 0;
 6     int psLen = strlen(patternString);
 7 
 8     if(hash == NULL) return NULL;
 9 
10     memset(hash, 0, 256 * sizeof(long long));
11     for(idx = 0; idx < psLen; ++idx)
12     {
13         hash[(unsigned int)patternString[idx]] |= ((long long)1 << idx); //表示patternString[idx]代表字符可以是在模式串的哪些位置
14     }
15 
16     return hash;
17 }
18 
19 //the patternString length must be less than 64
20 MatchingInfo * ShiftAnd(char *patternString, char *dataString, unsigned int dsLen)
21 {
22     unsigned int idxDs = 0, psLen = strlen(patternString);
23     long long *hash = initAlphbat(patternString);
24 
25     long long prefix = 0;  //每一位表示一个模式串的前缀，如果该位是1则表示当前该前缀被匹配上
26 
27     if(hash == NULL) return NULL;
28 
29     //匹配信息的初始化
30     MatchingInfo *mi = (MatchingInfo *)malloc(sizeof(MatchingInfo));
31     if(mi == NULL) return NULL;
32     mi->indexOfMatch = (unsigned int *)malloc(sizeof(unsigned int));
33     mi->numOfMatch = 0;
34     mi->allocLen = 1;
35 
36     //下面的循环中动态更新prefix
37     for(idxDs = 0; idxDs < dsLen; ++idxDs)
38     {
39         prefix = (prefix << 1) | 1;
40         prefix &= hash[(unsigned int)dataString[idxDs]];
41         if(prefix & ((long long)1 << (psLen - 1)))
42         {
43             //匹配上一个模式串
44             if(mi->allocLen > mi->numOfMatch)
45             {
46                 //记录下标的内存够用
47                 mi->indexOfMatch[mi->numOfMatch++] = idxDs - psLen + 1;
48             }
49             else
50             {
51                 //扩张匹配下标的内存
52                 mi->indexOfMatch = (unsigned int *)realloc(mi->indexOfMatch, (mi->allocLen << 1) * sizeof(unsigned int));
53                 mi->allocLen <<= 1;
54                 mi->indexOfMatch[mi->numOfMatch++] = idxDs - psLen + 1;
55             }
56         }
57     }
58 
59     free(hash);
60     hash = NULL;
61     return mi;
62 }