题目描述 

Description

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

输入描述 

Input Description

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

输出描述 

Output Description

仅一行一个整数

样例输入 

Sample Input

abcd bc

样例输出 

Sample Output

2

数据范围及提示 

Data Size & Hint

字符串的长度均不超过100

 

代码：

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

using namespace std;

string a,b;

int n,m,p[105]={0};

int main()

{

cin>>a;

cin>>b;

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[i]==b[j+1])

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 (a[i]==b[j+1])

j++;

if (j==m)

{

printf("%d",i-m+1);

break;

}

}

}