串的匹配模式算法（KMP）

算法：是对特定问题求解步骤的一种描述。

既然是对特定问题的一种解决方案，那我们就先来构造一下这个特定问题和问题出现的场景。

场景：不管是写C，C++， Objective-C，Java等等我想大家一定写过模糊查询，即在某一个主串中查找一个子串，或者判断中串是否存在主串中的算法。

问题：在实际编码中也许你是直接调用系统自身的API完成的这件事情。但是我们今天想探讨一下，如果让我们自己来编写这一算法，该如何来完成这一工作。

1.算法目的

求子串在主串中的位置。子串的定位操作通常称为串的匹配模式，是各种串处理系统中最重要的操作之一。

2.回逆算法

//返回子串subStr在主串sourceStr中的位置
int getIndex(char sourceStr[], char subStr[]) {
    
    int i = 0;
    int j = 0;
    int sorrceStrLength = (int)strlen(sourceStr);
    int subStrLength = (int)strlen(subStr);
    while (i < sorrceStrLength && j < subStrLength) {
        
        if (sourceStr[i] == subStr[j]) {
            
            i++;
            j++;
        } else {
            
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= subStrLength ) {
        
        return i - subStrLength;
    }
    return -1;
}

算法的基本思想：主串的第0个字符起与子串的第0个字符起相比较，如果相等则继续比较后续字符。否则主串回退到此轮比较的首字符的下一字符再次进行匹配。依次类推，直到首次出现子串中的每个字符依次和主串中的一个连续的字符序列相等，此时返回这个连续字符序列的首字符在主串中的位置。否则返回-1表示匹配失败。
当然，有同学该提出问题了，如果主串中有多个这样的连续字符序列该怎么办。

如果需求像上面同学所问。那么我们在主串中遇到子串的时候就不能返回。而是要将这个字符记录下来，等匹配玩整个主串的时候一起返回。这样的话我们上诉代码也不需要做太大的改变。只需将while循环改写成两个while的嵌套。

while (i < sourceStrLength) {
    while (i < sorrceStrLength) {
        
        j = 0;
        while (j < subStrLength) {
            
            if (sourceStr[i] == subStr[j]) {
                
                i++;
                j++;
            } else {
                
                i = i - j + 1;
                j = 0;
            }
        }
        if (j >= subStrLength ) {
            
            //记录匹配到的子串首元素在主串中的位置。
        }
    }
}

上述匹配过程易于理解，且在某些应用场合，如文本编辑等，效率也是比较高。例如：在判断sting是否纯在于a string searching example consisting of simple text中。如果利用上述算法，则while的循环次数，即进行单个字符比较的次数为41次。只有加粗字符需要比较两次其余只需要比较一次 a string searching example consisting of simple text。在这种情况下，此算法的效率还是会比较高的。

然而在有些情况下该算法的效率极低。例如如：主串是“000001” 子串“001”

第一趟：    
000001        i = 2
001           j = 2          此时i要回退到 i=i-j+1=1处
第二趟：
000001        i=3
 001          j=2            此时i要回退到 i=i-j+1=2处
第三趟：
000001        i=4
  001         j=2            此时i要回退到 i=i-j+1=3处
第四趟：
000001        i=5            
   001        j=2            无需回退，返回下标i-j=3
   

这种情况下算时间法复杂度是O((n-m+1)*m)。在二进制计算机上，实际处理的都是01串。一个字符也可以看成8为二进制的01串。包括汉字存储在计算机中处理的时候也是作为一个01串和其他是我字符串一样看待。因此下面我讲重点来优化上述算法，让时间复杂度降到常量级。

3.KMP算法

从上述算法的执行过程不难发现，由于主串的回退，从而造成了比较次数的增加。因此我们的目的就很明确，即减少和消除回退这一步骤。
优化方案（KMP算法）：每当一趟匹配过程中出现字符比较不等时，不需将i回退到此趟比较首元素的下一位，而是利用已经得到的部分匹配的结果将子串尽可能向右滑动，然后继续进行比较。那我们下面就拿一个例子来讲解

主串：ababcabcacbab
子串：abcac

第一趟匹配：
ababcabcacbab           i=0 -----> i=2
abc                     j=0 -----> j=2

第二趟匹配：
ababcabcacbab           i=3 -----> i=6 
   abcac                j=0 -----> j=4
   
第三趟匹配：
ababcabcacbab           i=7 -----> i=10
     abcac              j=1 -----> j=4        在此趟匹配中子串首元素和第二个元素(ab)并没有参与比较

从上面不难看出，在真个比较过程中主串没有回退这个步骤，子串也没有在每次此匹配失败之后，回到首元素再次比较，而是到特定位序的元素去比较。那么问题有出现了，我们该如去找到这个特定位序元素。

特定位序的求法

如主串A1A2A3...An,子串B1B2B3...Bn

假设在匹配失败时，子串中第k个元素继续比较，则会出现下列关系式A1A2...Ak = B(i-k)B(i-k+1)...B(i)

而已经得到的部分匹配结果是A(j-k)A(j-k+1)...A(j) = B(i-k)B(i-k+1)...B(i)

故 A1A2...Ak = A(j-k)A(j-k+1)...A(j)

j        |0 1 2 3 4 5 6 7
子串      |a b a a b c a c
特定位序   |0 0 0 1 1 2 0 1

那么下面我们来用C语言编写上述得到特定位序的算法

void getnext(char subStr[], int next[]){
    
    int i=0;
    int j=-1;
    next[0]=-1;
    while(i<strlen(subStr)){
        
        if(j==-1||subStr[i]==subStr[j]){
            
            i++;
            j++;
            next[i] = j;
        } else {
            
            j=next[j];
        }
    }
    next[0] = 0;
}

根据上面对回逆算法不合理地方的分析，我们得出KMP算法。那么我们就来用C语言实现一下KMP算法。

int index_KMP(char sourceStr[], char subStr[], int next[]){
    
    int i = 0;
    int j = 0;
    while(i < strlen(sourceStr) && j < strlen(subStr)) {
        
        if(j == 0 || sourceStr[i] == subStr[j]){
            
            i++;
            j++;
        } else {
            
            j=next[j];
        }
    }
    if (j == strlen(subStr)) {
        
        return i - (int)strlen(subStr);
    } else {
        
        return -1;//匹配失败
    }
}

我只可以直接边用这个连个函数实现主串和子串之间的匹配

int main() {

    char sourceStr[] = "abaaabaabcacbab";
    char subStr[] = "abaabcac";
    int next[(int)strlen(subStr)];    
    getNext(subStr, next);
    int index = index_KMP(sourceStr, subStr, next);
    printf("index = %d", index);
    return 0;
}

好今天我们的KMP算法就分析到这里。
[相关代码] https://github.com/LHCoder2016/KMP.git
[欢迎讨论] huliuworld@yahoo.com