题目描述 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用户请注意：两个字符串之间可能包含多个空格
分类标签 Tags 点此展开
注意：依旧是模板，但是这次是自己打的，发现了一些问题，WA了两次因为输出SB了233
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; char a[],b[];
int lena,lenb,sp[]; void calcsp()
{
int t;
sp[]=-;
for (int i=;i<lena;i++)
{
t=sp[i];
while (t!=- && a[t]!=a[i]) t=sp[t]; //注意是&&
sp[i+]=++t;
}
} void kmp()
{
int t=,k=;
calcsp();
while (t<lena && k<lenb)
{
if (k==- || a[t]==b[k]) t++,k++; //注意从头匹配k==-1
else k=sp[k];
if (k==lenb) cout<<t-lenb+<<endl,t=0x7f;
}
} int main()
{
cin>>a>>b;
lena=strlen(a);
lenb=strlen(b);
kmp();
return ;
}