数据结构-串，KMP算法笔记

一、基本概念

二、模式串匹配

1、朴素（暴力）算法：

用模式串从主串的第一个字符开始对照匹配，匹配成功继续下一个字符，失败就回到主串的第二个字符重新匹配，一直到完全匹配结束。
算法实现：

int find_sub_string(string s, string t)
{
   int i = 0, j = 0;    //初始化两个指针
   while(i<s.size() && j<t.size()){
       if(s[i] == t[j]){
           i++;    //如果两个指针指向的字符相等
           j++;    //则将两个指针向后移动
       }
       else{
           i = i - j + 1;    //匹配失败，i退回到上次匹配首位的下一位
           j = 0;            //j退回到子串首位
       }
   }
   if(j>=t.size()){    //j走到子串末尾说明匹配成功
       return i - j;    //匹配成功返回主串中子串出现的第一位
   }
   else 
       return -1;        //匹配失败，返回-1
}

（重点）KMP算法：

一、计算next数组方法：

1、手动计算：
统计每个子串的最长公共前后缀，例，ABABA
前缀：A，AB，ABA，ABAB
后缀：A，BA，ABA，BABA
先算出每个子串的部分匹配值PM：0，0，1，2，3
再将部分匹配值右移，用-1补空缺得到next数组。
所以上面对应的next数组（以0开头为下标的）为：-1，0，0，1，2
每个位置加1得到以1开头为下标的next数组：
0，1，1，2，3

2、根据公式计算：
把主串标上标1，2，3.....
默认next[1]=0，next[2]=1
开始求后面的next[3]......
公式：比较上一个字符值和它对应的next数组指向的字符值
相同的话所求字符的next数组值就是上一个next数组值是+1，
不相同就根据next数组指向一直向前找，直到找到相等的就使用找到的next数组值加1。

void get_Next(string s, int next[])        //这个函数对字符串s进行预处理得到next数组
{
    int j = 0;
    next[0] = 0;    //初始化
    for(int i = 1; i<s.size(); i++){    //i指针指向的是后缀末尾，j指针指向的是前缀末尾
        while(j>0&&s[i]!=s[j])    j = next[j-1];    //前后缀不相同，去找j前一位的最长相等前后缀
        if(s[i]==s[j])    j++;    //前后缀相同，j指针后移
        next[i] = j;    //更新next数组
    }
}
int strSTR(string s, string t)    //这个函数是从s中找到t，如果存在返回t出现的位置，如果不存在返回-1
{
    if(t.size()==0)    return 0;
    get_Next(t, next);
    int j = 0;
    for(int i = 0; i < s.size(); i++){
        while(j>0&&s[i]!= t[j])    j = next[j-1];    
        if(s[i]==t[j])    j++;
        if(j==t.size())    return i - t.size() + 1;
    }
    return -1;
}

二、nextval数组求解：
先求出next数组，才能求nextval数组。
找到不相等的元素将next数组赋值给nextval数组。
相等的元素要一直向前找
和next数组区别：
next数组是找相等的字符赋值
nextval是找不相等的字符赋值

三、KMP算法失配分析
主串的指针是不会改变的，子串的指针移动到next数组所对应的值，重新开始匹配。