第四章

题目：串的模式匹配

给定一个主串S（长度<=10^6）和一个模式T（长度<=10^5），要求在主串S中找出与模式T相匹配的子串，返回相匹配的子串中的第一个字符在主串S中出现的位置。

（用KMP算法，就是不用再回溯，

最前面的k个字符和j之前的最后k个字符是一样的：P[1~ k] == P[j-k ~ j-1]）

1、先定义一个串的顺序存储结构，因为不需要出插入和删除操作，所以选用了顺序存储

typedef struct {    char ch[maxlen + 2];    int length;}sstring;

2、为了方便自己对于kmp的理解，所以用以下代码来实现数组下标从1开始

void add(sstring &s, char temp[]) {       s.ch[0] = ' ';    strcat(s.ch, temp);    s.length = strlen(s.ch) - 1;}

3、按照题目要求写了一部分主函数

int main() {  int result = 0;     cin >> temp;    add(s, temp);    cin >> temp;    add(t, temp);    需要一个求位置的函数    求位置时在回溯过程中需要一个知道回溯到哪里的函数 }

发现需要两个函数，于是开始写下面的函数

4、用一个函数来求模式串的next函数并存入数组nextval。

其中有个初始化如下，我起初不理解，后面想明白了：j已经在最左边了，不可能再移动了，所以这时候要应该是i指针后移

nextval[1] = 0;

找到next函数的主要过程：

while (i < t.length) {  //t为模式串        if (j == 0 || t.ch[i] == t.ch[j]) {  //相同则继续往后移，找到最长相同前后缀            j++;            i++;            if (t.ch[i] != t.ch[j]) {  //前面已经+1，匹配下一个是否相等，                nextval[i] = j;  //如果不同  把j位置给next            }            else {  //如果相同                nextval[i] = nextval[j];  //则i 的位置等于j的位置，最长相同前后缀同时加            }        }        else  //如果不等，则重置j            j = nextval[j];//next[j]为之前最长相同前后缀    }

主要是：

当T[i] != P[j]时，有T[i-j ~ i-1] == P[1 ~ j]，由P[1 ~ k] == P[j-k ~ j-1]   —>  必然：T[i-k ~ i-1] == P[1 ~ k]

5、利用模式串T的next函数求T在主串S中第几个字符之后的位置。

1）表示位置相同的变量

int result = 0;

2）如果相同则右移

if (j == 0 || s.ch[i] == t.ch[j]) {             j++;            i++;        }

3）不同则回溯

else {            j = nextval[j];         }

4）匹配成功时，result即为第一个字符出现的位置

if (j > t.length) {  //当最后匹配成功就是比主串多1时        result = i - t.length;    }

6、写完函数后写函数声明

oid add(sstring &s, char temp[]);void getnext(sstring T, int next[]);int KMP(sstring s, sstring t, int next[]);

7、补充主函数

int main(){    int result = 0;    cin >> temp;    add(s, temp);    cin >> temp;    add(t, temp);    getnext(t, nextval);    result = KMP(s, t, nextval);    cout << result;    return 0;}