KMP

1204 寻找子串位置
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 青铜 Bronze
题解
题目描述 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 点此展开

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
#define LL long long
int read()
{
	int s=0,f=1;char ch=getchar();
	while(!('0'<=ch&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*f;
}
int n,m,fail[100005];
char a[100005],b[100005];
int main()
{
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1);
	m=strlen(b+1);
	for(int i=2,j=0;i<=m;i++)
	   {
	    while(j&&b[j+1]!=b[i])j=fail[j];
	    j+=(b[j+1]==b[i]);
	    fail[i]=j;
	   }
	for(int i=1,j=0;i<=n;i++)
	   {while(j&&b[j+1]!=a[i])j=fail[j];
	    if(b[j+1]==a[i])j++;
	    if(j==m)
	       {printf("%d\n",i-m+1);
	        break;
		   }
	   }
	return 0;
}