在日常生活中我们常常会遇见在一篇文章中找关键词的事情。如果用程序来解决你会怎么做？？？
ps：假设文章字段为t， 关键词为p

暴力解法：

枚举文章中的每一个点，然后往后匹配是非为关键字？？？
就像这样， 挨个匹配每个字符。

int lent = strlen(t);
int lenp = strlen(p);
for(int i = 0; i < lent; i++)
{
    int flag = 1;//是否成功匹配
    if(i + j >= lent) break;
    for(int j = 0; j < lenp; j++)
    {
        if(t[i+j] != p[j])//匹配失败
        {
            flag = 0;
            break;
        }
    }
    if(flag) printf("%d", i-lenp+1);//输出匹配成功了的位置
}

显然复杂度是o(n^2)的，会耗费大量的时间。

KMP算法：

ps：从下表为1得位置开始储存p和t。(这样会更加方便)
暴力算法之所以耗费大量的时间，是因为常常会发生这样的现象：经过千辛万苦匹配到了p的最后一个字符，结果这时候不匹配了，于是乎向右移动一格，然后重头开始匹配。

nex数组：
那么如果我们可以使得在匹配失败后向右移动很长的一段距离，那么就可以节省大量的时间了。
由此我们为p定义一个nex数组，nex[i]的含义为nex[i]的含义为以p[i]j结尾的后缀，能够匹配的从1开始非平凡前缀的最大坐标， 非平凡的意思是不能是p本身。也就是说，找到最大的长度，p的前缀和以p[i]为结尾的后缀相同。
例子：
比如对于abab
nex值分别为0 0 1 2
对于aaaa
nex值分别为0 1 2 3

算法过程：
如果现在正在尝试匹配t[i] 和 p[j+1]，如果这个时候匹配失败，那么可以直接令j = nex[j], 然后继续判断t[i] 是否等于p[j+1], 直到他们相等或者j为0。
t[i] == p[j+1] 的意思已经通过nex[j]找到了了一个前缀仍然匹配了t以t[i-1]结尾的后缀，此时t[i] == p[j+1]， 说明对于j+1已经匹配成功了，可以开始下一个字符的匹配了。
j == 0的意思是这个时候p无法继续向右移动了，已经到头了，然后也可以不需要继续匹配了。

匹配的代码：

void kmp()
{
    int lent = strlen(t+1);
    int lenp = strlen(p+1);
	//尝试用t[i]与p[j+1]进行匹配
    for(int i = 1, j = 0; i <= lent; i++)
    {
        while(j && t[i] != p[j+1]) j = nex[j];
        if(t[i] == p[j+1]) j++;
        if(j == lenp)
        {
            printf("%d\n", i-lenp+1);//输出成功匹配的起始下表
            j = nex[j];
        }
    }
}

假设现在在ABABABC上匹配ABA(下标都从1开始)
ABA的nex值为0 0 1
初始时i == 1, j == 0（因为用t[i] 与 p[j+1]进行匹配, 这样初始化表示从p和t第一个字符开始匹配）
匹配过程：
i == 1, j == 0 : t[i] == p[j+1]
i == 2, j == 1 : t[i] == p[j+1]
i == 3, j == 2 : t[i] == p[j+1] (输出下表1并j = nex[j])
i == 4，j == 1 : t[i] == p[j+1]
i == 5, j == 2: t[i] == p[j+1] (输出下表3并j = nex[j])
i == 6, j == 1: t[i] == p[j+1]
i == 7, j == 2: t[i] != p[j+1] （j = nex[j])
i == 7, j == 1: t[i] != p[j+1] （j = nex[j])
i == 7, j == 0: 跳出循环
结束匹配
最终i == 8, j == 0

注意项: 为什么nex的值时最长的前缀，而不能是比最长要小一点，因为j = nex[j]其实是相当与把p直接向右移动一大段距离，而是的nex值越长，其实是为了移动的距离小一点，防止造成匹配的遗漏。

构建nex数组:

nex数组的构建与匹配过程基本相同，我们是通过从下标1开始遍历，逐个获取每个位置的nex值，也就是说当我们需要求nex[i]时， nex[1] 到nex[i-1] 的值都已经求到了，如果我们可以用i之前的nex值求得i得nex值，那就可以了。。那么根据nex的定义，如果现在要求nex[i]， 而j在每一次迭代后等于nex[i-1]。
说明现在以j结尾得前缀是仍然是和i-1结尾得后缀相同得，如过现在p[i]等于p[j+1]，则nex[i] 等于j+1，否则继续j = nex[j]。
如果最后j = 0, 那么说明找不到一个长度至少为1得前缀与以p[i]为后缀的字符串相同， 此时nex[i] 等于0。
例如:
求ABABABC的第六个字符nex值。
前五个nex值为0 0 1 2 3
根据nex[5]我们可以找到一个前缀和与下标5为后缀相同，也就是ABA, 因为第四位恰好时B与第六位相同， 那么就找到了最大的前缀。所以nex[6]为4。

下面是代码

void getnex()
{
    int lenp = strlen(p+1);
    for(int i = 2, j = 0; i <= lenp; i++)
    {
        while(j && p[i] != p[j+1]) j = nex[j];
        if(p[i] == p[j+1]) j++;
        nex[i] = j;
    }
}

模板题
例题：传送门
解析：

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
char t[N], p[N];
int nex[N];

void getnex()
{
    int lenp = strlen(p+1);
    for(int i = 2, j = 0; i <= lenp; i++)
    {
        while(j && p[i] != p[j+1]) j = nex[j];
        if(p[i] == p[j+1]) j++;
        nex[i] = j;
    }
}

void kmp()
{
    int lent = strlen(t+1);
    int lenp = strlen(p+1);

    for(int i = 1, j = 0; i <= lent; i++)
    {
        while(j && t[i] != p[j+1]) j = nex[j];
        if(t[i] == p[j+1]) j++;
        if(j == lenp)
        {
            printf("%d\n", i-lenp+1);
            j = nex[j];
        }
        printf("%d %d\n", i , j);
    }
}

int main()
{
    scanf("%s%s", t+1, p+1);
    getnex();
    kmp();
    int lenp = strlen(p+1);
    for(int i = 1; i <= lenp; i++) printf("%d ", nex[i]);
}

这题有点小难。
例题：传送门
解析：

#include <bits/stdc++.h>

using namespace std;
const int N = 5e6+10;
int nex[N];
char t[N], p[N];
int now;

void get_nex()
{
    int len = strlen(p+1);
    for(int i = 2, j = 0; i <= len; i++)
    {
        while(j && p[i] != p[j+1]) j = nex[j];
        if(p[i] == p[j+1]) j++;
        nex[i] = j;
    }
}

int kmp(char *p, char *t)
{
    int j = 0;
    int lent = now;
    int lenp = strlen(p+1);
    int st = max(lent - lenp+1, 1);
    for(int i = st; i <= lent; i++)
    {
        while(j && t[i] != p[j+1]) j = nex[j];
        if(t[i] == p[j+1])
        {
             j++;
        }
    }
    return j;
}

int main()
{
    int n;
    scanf("%d", &n);
    scanf("%s", t+1);
    now = strlen(t+1);
    for(int i = 2; i <= n; i++)
    {
        scanf("%s", p+1);
        get_nex();
        int j = kmp( p, t);
        int lenp = strlen(p+1);
        for(int i = j + 1; i <= lenp; i++) t[++now] = p[i];//从最终重复起始位置挨个把字符复制进t中
        t[now+1] = '\0';
    }
    printf("%s", t+1);
    return 0;
}