6-2 模式匹配 (10分)

6-2 模式匹配 (10分)
给出主串s和模式串t，其长度均不超过1000。本题要求实现一个函数BF(string s, string t)，求出模式串t在主串s中第一次出现的位置（从0开始计算），如果在s中找不到t，则输出-1。

函数接口定义：
/* s为主串，t为模式串。

• 函数返回t在s中第一次出现的位置。
  */
  int BF(string s, string t);
  其中 s 和 t 分别为主串和模式串，长度均不超过1000。函数返回模式串t在主串s中第一次出现的位置（从0开始计算），如果在s中找不到t，则输出-1。

裁判测试程序样例：
#include <bits/stdc++.h>
using namespace std;

/* s为主串，t为模式串。

• 函数返回t在s中第一次出现的位置。
  */
  int BF(string s, string t);

int main(int argc, char const *argv[])
{
string s, t;
getline(cin, s); //输入主串
getline(cin, t); //输入模式串
int pos = BF(s, t); //搜索
cout << pos << endl;//输出模式串在主串中第一次出现的位置
return 0;
}

/* 请在这里填写答案 */
输入样例1：
This is a test string
is
输出样例1：
2
输入样例2：
This is a test string
The
输出样例2：
-1

/* s为主串，t为模式串。
 * 函数返回t在s中第一次出现的位置。
 */
vector<int>getNext(const string&str)
{
    vector<int>next(str.size());
    next[0]=-1;
    for(int i=1,j=-1;i<str.size();i++){
        while(j!=-1&&str[i]!=str[j+1]){
            j=next[j];
        }if(str[i]==str[j+1]){
            j++;
        }next[i]=j;
    }return next;
}
int kmp(const string&strOne,const string&strTwo){
    vector<int>strTwoNext=getNext(strTwo);
    for(int i=0,j=-1;i<strOne.size();i++){
        while(j!=-1&&strOne[i]!=strTwo[j+1]){
            j=strTwoNext[j];
        }if(strOne[i]==strTwo[j+1])j++;
        if(j==strTwo.size()-1){
            return i-strTwo.size()+1;
        }
    }return -1;
}
int BF(string s, string t)
{
    return kmp(s,t);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30