KMP 串的模式匹配 (25分)（3種方法）

給定兩個由英文字母組成的字串 String 和 Pattern，要求找到 Pattern 在 String 中第一次出現的位置，並將此位置後的 String 的子串輸出。如果找不到，則輸出「Not Found」。

本題旨在測試各種不同的匹配演演算法在各種資料情況下的表現。各組測試資料特點如下：

資料0：小規模字串，測試基本正確性；
資料1：亂資料，String 長度為 10​5，Pattern 長度為 10；
資料2：亂資料，String 長度為 10​5，Pattern 長度為 102；
資料3：亂資料，String 長度為 10​5，Pattern 長度為 10​3；
資料4：亂資料，String 長度為 10​5，Pattern 長度為 10​4；
資料5：String 長度為 10​6，Pattern 長度為 105；測試尾字元不匹配的情形；
資料6：String 長度為 106 ，Pattern 長度為 105 ；測試首字元不匹配的情形。
輸入格式:
輸入第一行給出 String，為由英文字母組成的、長度不超過 10​6 的字串。第二行給出一個正整數 N（≤10），為待匹配的模式串的個數。隨後 N 行，每行給出一個 Pattern，為由英文字母組成的、長度不超過 10​5的字串。每個字串都非空，以回車結束。

輸出格式:
對每個 Pattern，按照題面要求輸出匹配結果。

輸入樣例:

abcabcabcabcacabxy
3
abcabcacab
cabcabcd
abcabcabcabcacabxyz

輸出樣例:

abcabcacabxy
Not Found
Not Found

方法一：c++，主要使用字串擷取函數，超時，21分

#include <iostream>
#include <string>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	string s,p;
	int n;
	cin >> s;
	cin >> n;
	for(int i = 0;i<n;i++){
		cin >> p;
		bool flag = false;
		if(p.length()>s.length())
			cout << "Not Found" << endl;
		else{
			for(int j = 0;j<=s.length()-p.length();j++){
				if(s[j]==p[0]){
					string ss = s.substr(j,p.length());
					if(ss==p){
						cout << s.substr(j) << endl;;
						flag = true;
						break;
					}
				}
			}
			if(!flag)
				cout << "Not Found" << endl;
		}
	}
	return 0;
} 

方法二：學到了一個新的函數，挺好用的，厲害啊！！！附上一篇講解的部落格，注意它的引數是char陣列（根據題目資料的要求，選擇陣列需要開闢的大小），不要把string往裡邊放！！！，同時注意它的標頭檔案

strstr(str1,str2) 函數

#include <iostream>
#include <cstring>
using namespace std;

int main(){
	char s[1000001],p[100001];
	int n;
	cin >> s;
	cin >> n;
	for(int i = 0;i<n;i++){
		cin >> p;
		if(strstr(s,p))
			cout << strstr(s,p) << endl;
		else
			cout << "Not Found" << endl;
	}
	return 0;
}

方法三：按照題目要求乖乖來，使用KMP演演算法，不要用暴力BF哦（資料大肯定會超時的）

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int xnext[100001];

void get_next(string s){
	int i,j;
	i = 0;//字尾
	j = -1;//字首
	xnext[0] = -1;
	while(i<s.length()){
		if(j==-1||s[i]==s[j]){
			i++;
			j++;
			xnext[i] = j;
		}
		else
			j = xnext[j];
	} 
}

int get_index(string s1,string s2){
	int i = 0;
	int j = 0;
	get_next(s2);
	while(i<s1.length()){
		if(j==-1||s1[i]==s2[j]){
			i++;
			j++;
		}
		else
			j = xnext[j];
		if(j==s2.length())
			return i-s2.length();
	}
	return -1;
}

int main(){
	string s,p;
	int n;
	cin >> s;
	cin >> n;
	for(int i = 0;i<n;i++){
		cin >> p;
		int res = get_index(s,p);
		if(res==-1)
			cout << "Not Found" << endl;
		else
			cout << s.substr(res) << endl;
	}
	return 0;
}