給定兩個由英文字母組成的字串 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/154100.html
標籤：其他
上一篇：Flutter 解答StackOverflow問題flutter scrollable list below rendered image