NOIP2018模拟赛2018.10.22】最大跨距

题目

题解

–明显是字符串匹配
kmp啦
模板上套

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;

char s[MAXN],s1[MAXN],s2[MAXN];
int l,l1,l2;
int next[MAXN];
int x1=-1,x2=-1;

void getnext(char *s,int l){
	next[0]=-1;
	int j=-1;
	for(int i=1;i<l;i++){
		while(j!=-1&&s[j+1]!=s[i])
			j=next[j];
		if(s[j+1]==s[i])
			j++;
		next[i]=j;
	}
}

int kmp(char *s,int l,char *ss,int ll){
	getnext(ss,ll);
	int j=-1;
	for(int i=0;i<l;i++){
		while(j!=-1&&ss[j+1]!=s[i])
			j=next[j];
		if(ss[j+1]==s[i])
			j++;
		if(j==ll-1)
			return i-ll+1;
	}
	return -1;
}

int main(){
//	freopen("dis.in","r",stdin);
//	freopen("dis.out","w",stdout);
	while(s[l++]=getchar()){
		if(s[l-1]==',')
			break;
	}
	l--;
	while(s1[l1++]=getchar()){
		if(s1[l1-1]==',')
			break;
	}
	l1--;
	cin>>s2;
	l2=strlen(s2);
	x1=kmp(s,l,s1,l1);
	if(x1==-1){
		cout<<-1;
		return 0;
	}
	x1+=l1-1;
	reverse(s,s+l);
	reverse(s2,s2+l2);
	x2=kmp(s,l,s2,l2);
	x2=l-x2-l2;
	if(x1>=x2)
		cout<<-1;
	else
		cout<<x2-x1-1;
	return 0;
}