第4章学习小结_串(BF&KMP算法)、数组（三元组）

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

  输入格式:  输入有两行： 第一行是主串S； 第二行是模式T.

  输出格式:     输出相匹配的子串中的第一个字符在主串S中出现的位置。若匹配失败，输出0.

输入样例:

在这里给出一组输入。例如：

aaaaaba
ba

输出样例:

在这里给出相应的输出。例如：6

int BF(string A,string B)//这里算法是从下标为0开始，所以跟书里有点不同
{
    int i=0,j=0;
    while(iB.length())
    {
        if(A[i]==B[j])
        {
            ++i;++j;
        }
        else 
        {
            i=i-j+1;j=0;//根据上面分析，下标后退进行比较
        }
    }
    if(j>=B.length()) return i-j+1; //返回匹配成功第一个位置
    return 0;
}

View Code

我感觉用下标比较容易操作，只需要改一下相应的位置，然后直接用C++定义字符串string，再输入字符串，相对也比较简洁。

主函数如下：

int main()
{
    string a,b;
    getline(cin,a);//输入一个串之后回车就可以输入下一个串
    getline(cin,b);
    //int num=BF(a,b);
        //int num=KMP(a,b);这里两个选一个，下面KMP算法的主函数一样
    cout<<num;
    return 0;
 } 

View Code

这道题用BF算法可以简单就解决了，那为啥还要有KMP算法呢？

　　一般情况下，BF算法时间复杂度为O（m*n），数据量不大时候，执行时间近似为O（m+n）,但如果是庞大数据，那它的效率就很低了，我们老师专门设了一个测试点主串长度100万，模式长度10万，而且是那种主串为aaaaaaaa...,模式串是ba......。所以，从第一个字符比较一直不匹配，而模式串一直回溯到j=0,这样工作量超大，所以上面BF算法提交之后在这个测试点是运行超时的。

这样，才有优化算法KMP,第一次看的时候一脸懵，无法理解三个大牛的逻辑思维。所以我搜索了几篇博客认真学习，试图融入大牛的思维世界。

（链接：https://blog.csdn.net/henuyx/article/details/44653799、https://www.cnblogs.com/tangzhengyue/p/4315393.html）

2、KMP算法

这种改进算法是由D.E.Knuth、J.H.Morris、V.R.Pratt三位大牛同时设计实现的。下面我就捋一下我入门的思路方法。

　　KMP最让人难以理解就是它的next数组是如何得到的，开始我觉得很神奇，next数组居然实现了字符匹配的“跳转”。举个例子，看看是如何算出next数组的。

模式串  a b a a b c a c

下标 j  0 1 2 3 4 5 6 7