给定两个由英文字母组成的字符串 String 和 Pattern，要求找到 Pattern 在 String 中第一次出现的位置，并将此位置后的 String 的子串输出。如果找不到，则输出“Not Found”。
本题旨在测试各种不同的匹配算法在各种数据情况下的表现。各组测试数据特点如下：
- 数据0：小规模字符串，测试基本正确性；
- 数据1：随机数据，String 长度为 10510^5105，Pattern 长度为 101010；
- 数据2：随机数据，String 长度为 10510^5105，Pattern 长度为 10210^2102；
- 数据3：随机数据，String 长度为 10510^5105，Pattern 长度为 10310^3103；
- 数据4：随机数据，String 长度为 10510^5105，Pattern 长度为 10410^4104；
- 数据5：String 长度为 10610^6106，Pattern 长度为 10510^5105；测试尾字符不匹配的情形；
- 数据6：String 长度为 10610^6106，Pattern 长度为 10510^5105；测试首字符不匹配的情形。
输入格式:
输入第一行给出 String，为由英文字母组成的、长度不超过 10610^6106 的字符串。第二行给出一个正整数 NNN（≤10\le 10≤10），为待匹配的模式串的个数。随后 NNN 行，每行给出一个 Pattern，为由英文字母组成的、长度不超过 10510^5105 的字符串。每个字符串都非空，以回车结束。
输出格式:
对每个 Pattern，按照题面要求输出匹配结果。
输入样例:
abcabcabcabcacabxy
abcabcacab
cabcabcd
abcabcabcabcacabxyz
输出样例:
abcabcacabxy
Not Found
Not Found
解题思路：看到这道题无疑就是用kmp算法；下面的代码就是kmp算法的模板➕用一个ans记录它是否找到；
具体的kmp算法思想在我前面的博客有：链接如下：
https://www.cnblogs.com/yewanting/p/10674340.html
代码如下：
#include<iostream>
#include<stdio.h>
using namespace std; int next1[];
void getnext(string t ,int tsize)
{
int k = - ;
int j = ;
next1[] = -;
while(j<tsize-)
{
if(k==-||t[j] == t[k])
{
++j;
++k;
next1[j] = k;
}else
k = next1[k]; }
} int kmp(string s ,string t ,int ssize,int tsize)
{
int i = ;
int j = ;
while(i<ssize&&j<tsize)
{
if(j==-||s[i]==t[j])
{
i++;
j++;
}else
{
j = next1[j];
}
}
if(j==tsize)
{
return i-j+;
}else
return -;
}
string s ;
string t ;
int n ;
int ssize;
int tsize;
int ans ;
int main()
{
cin>>s;
cin>>n;
ssize = s.size();
while(n--)
{
cin>>t;
tsize = t.size();
getnext(t,tsize);
ans = kmp(s,t,ssize,tsize); //用一个ans来记录是否找到匹配
if(ans==-) //若找不到
{
printf("Not Found\n");
}else //找到，则输出后面的字符；
{
for(int i = ans- ;i < ssize; i++)
{
cout<<s[i];
}
cout<<endl;
} }
return ;
}