Submission #243803

#	Time	Username	Problem	Language	Result	Execution time	Memory
243803		TadijaSebez	Necklace (Subtask 4) (BOI19_necklace4)	C++11	15 / 15	332 ms	504 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
const int N=3005;
char s[N],t[N];
int kmp[N],n,m;
void Build(){
	for(int i=2,j=0;i<=m;i++){
		while(j&&t[i]!=t[j+1])j=kmp[j];
		if(t[i]==t[j+1])j++;
		kmp[i]=j;
	}
}
void Go(int ans[]){
	for(int i=1,j=0;i<=n;i++){
		while(j&&s[i]!=t[j+1])j=kmp[j];
		if(s[i]==t[j+1])j++;
		ans[i]=j;
	}
}
int fw[N],bw[N];
array<int,3> Solve(){
	array<int,3> ans={0,0,0};
	for(int w=1;w<=m;w++){
		Build();Go(fw);
		reverse(t+1,t+1+m);
		reverse(s+1,s+1+n);
		Build();Go(bw);
		reverse(t+1,t+1+m);
		reverse(s+1,s+1+n);
		reverse(bw+1,bw+1+n);
		for(int i=1;i<=n;i++){
			int now=min(fw[i],m-w+1)+min(bw[i+1],w-1);
			if(ans[0]<now){
				ans={now,i-min(fw[i],m-w+1),w-min(bw[i+1],w-1)-1};
			}
		}
		char tmp=t[1];
		for(int i=2;i<=m;i++)t[i-1]=t[i];
		t[m]=tmp;
	}
	return ans;
}
int main(){
	scanf("%s %s",s+1,t+1);
	n=strlen(s+1);
	m=strlen(t+1);
	auto ans1=Solve();
	reverse(t+1,t+1+m);
	auto ans2=Solve();
	ans2[2]=m-ans2[2]-ans2[0];
	if(ans1[0]>ans2[0])printf("%i\n%i %i\n",ans1[0],ans1[1],ans1[2]);
	else printf("%i\n%i %i\n",ans2[0],ans2[1],ans2[2]);
	return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s %s",s+1,t+1);
  ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15