在这一章中，老师教了我们四种数据结构：BF算法，kmp算法，三元组和十字链表；还给我们讲了2019年团体天体赛中T1-8的AI题
1、对于BF和kmp算法，老师除了在课堂上讲解算法的主要核心思想外，还给了我们一道作业题去巩固；
这道题如下：
7-1 串的模式匹配 （30 分)
给定一个主串S（长度<=10^6）和一个模式T（长度<=10^5），要求在主串S中找出与模式T相匹配的子串，返回相匹配的子串中的第一个字符在主串S中出现的位置。
输入格式:
输入有两行： 第一行是主串S； 第二行是模式T.
输出格式:
输出相匹配的子串中的第一个字符在主串S中出现的位置。若匹配失败，输出0.
输入样例:
在这里给出一组输入。例如：
aaaaaba
ba
输出样例:
在这里给出相应的输出。例如：
6
首先，可以用BF算法去实现，但是BF算法是不能通过所有测试点的；BF算法实际上是一种暴力算法，而题目给的测试样例会有一个卡住而造成超时；
比如主串为aaaaaaaaaaaaaaaab 模式串为aaaaab ，这样的话每次都得去比较到最后一个才发现不匹配，而题目给的最大数据是1000000，所以一定是超时的；
BF算法代码如下：
我这里写的跟课本不太一样，我的i，j下标是从0开始，而课本的i，j表示的是位置，从1开始，所以当不匹配是课本回溯到的是i-j+2；而我这里是i-j+1；
#include<iostream>
#include<string.h>
using namespace std; string s , t;
int ssize ,tsize;
int i = ;
int j = ;
int main()
{
cin>>s; //输入主串
cin>>t; //输入模式串
ssize = s.size(); //主串的长度；
tsize = t.size(); //模式串的长度；
while(i<ssize&&j<tsize)
{
if(s[i]==t[j]) //如果匹配，则i++，j++；主串和模式串都向前移一位；
{
i++;
j++;
}else
{
i = i-j+; 否则主串回溯到i-j+1；
j = ; 模式串回溯到0；
}
}
if(j>=tsize)
{
cout<<i-tsize+;
}else
cout<<;
return ;
}
这道题还能用kmp算法去写，kmp的核心是next数值；
解题思路：串的模式匹配有两种：一种是BF算法，一种是KMP算法；
基于这道题给的数据，若用BF算法便会超时，所以我们这道题用KMP算法；
那么问题来了，KMP算法到底怎么用的；简单来讲，就是有两个步骤：
1、求模式串的next数组；
2、进行主串与模式串的匹配；
假设主串和模式串分别为
第一个问题：如何求next数组