「CODEVS1204」寻找子串位置(KMP)

2014年1月1日5,8773

题目描述 Description

给出字符串a和字符串b，保证b是a的一个子串，请你输出b在a中第一次出现的位置。

输入描述 Input Description

仅一行包含两个字符串a和b

输出描述 Output Description

仅一行一个整数

样例输入 Sample Input

abcd bc

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

字符串的长度均不超过100

Pascal用户请注意：两个字符串之间可能包含多个空格

代码

暴力不好玩，我们写个KMP吧

KMP参看KMP算法详解（M67教你KMP）

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int p[101];
int main()
{
    string a,b;
    cin>>a>>b;
    int n=a.length(),m=b.length();
    a=" "+a;b=" "+b;
    int j=0;
    for(int i=2;i<=m;i++)
    {
            while(j>0&&b[j+1]!=b[i])j=p[j];
            if(b[j+1]==b[i])j++;
            p[i]=j;
            }
    j=0;
    for(int i=1;i<=n;i++)
    {
            while(j>0&&b[j+1]!=a[i])j=p[j];
            if(b[j+1]==a[i])j++;
            if(j==m){printf("%d",i-m+1);break;}
            }
    return 0;
}