Submission #722144

#	Time	Username	Problem	Language	Result	Execution time	Memory
722144		jamezzz	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	209 ms	340 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define maxn 3005

int n,m,dp[maxn],len,apos,bpos,_len,_apos,_bpos;
int lps[maxn],flen[maxn],rlen[maxn];
char a[maxn],b[maxn];

void solve(int split,int &len,int &apos,int &bpos){
	
	for(int i=0;i<=n;++i)flen[i]=rlen[i]=0;
	for(int i=0;i<=m;++i)lps[i]=0;
	
	//kmp algorithm
	for(int i=1,pos=0;i<split;){
		if(b[i]==b[pos])lps[i++]=++pos;
		else if(pos>0)pos=lps[pos-1];
		else pos=0,++i;
	}
	lps[split]=split;
	for(int i=split+1,pos=split;i<m;){
		if(b[i]==b[pos])lps[i++]=++pos;
		else if(pos>split)pos=lps[pos-1];
		else pos=split,++i;
	}
	
	//printf("\nsplit %d\n",split);
	//printf("%s\n",b);
	//pf("lps: ");for(int i=0;i<m;++i)pf("%d ",lps[i]);pf("\n");
	
	for(int i=0,j=split;i<n;){
		if(j<m&&a[i]==b[j])flen[i++]=++j-split;
		else if(j>split)j=lps[j-1];
		else j=split,++i;
	}
	//pf("flen: ");for(int i=0;i<m;++i)pf("%d ",flen[i]);pf("\n");
	
	for(int i=n-1,j=0;i>=0;){
		if(j<split&&a[i]==b[j])rlen[i--]=++j;
		else if(j>0)j=lps[j-1];
		else j=0,--i;
	}
	//pf("rlen: ");for(int i=0;i<m;++i)pf("%d ",rlen[i]);pf("\n");
	
	for(int i=0;i<=n;++i){
		//printf("%d: %d\n",i,(i?flen[i-1]:0)+(i<n?rlen[i]:0));
		if((i?flen[i-1]:0)+(i<n?rlen[i]:0)>len){
			len=(i?flen[i-1]:0)+(i<n?rlen[i]:0);
			//printf("%d %d\n",flen[i-1],rlen[i]);
			apos=i-(i?flen[i-1]:0);
			bpos=split-(i<n?rlen[i]:0);
			//printf("%d %d\n",apos,bpos);
		}
	}
}

void solve(bool rev){
	for(int i=0;i<=m;++i){
		reverse(b,b+i);
		//original string is abcdef
		//reverse first part of string --> cba + def
		//match each string with some part of other string
		solve(i,_len,_apos,_bpos);
		if(_len>len){
			len=_len,apos=_apos,bpos=_bpos;
			//pf("%d %d\n",apos,bpos);
			if(rev)bpos=m-bpos-len;
		}
		reverse(b,b+i);
	}
}

int main(){
	sf(" %s",&a);sf(" %s",&b);
	n=strlen(a),m=strlen(b);
	
	solve(0);
	reverse(b,b+m);
	solve(1);
	
	pf("%d\n%d %d\n",len,apos,bpos);
}

/*
zxyabcd
yxbadctz

zxyabcd
xtcdabxy
*/

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:77:8: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[3005]' [-Wformat=]
   77 |  sf(" %s",&a);sf(" %s",&b);
      |       ~^  ~~
      |        |  |
      |        |  char (*)[3005]
      |        char*
necklace.cpp:77:21: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[3005]' [-Wformat=]
   77 |  sf(" %s",&a);sf(" %s",&b);
      |                    ~^  ~~
      |                     |  |
      |                     |  char (*)[3005]
      |                     char*
necklace.cpp:77:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  sf(" %s",&a);sf(" %s",&b);
      |    ^
necklace.cpp:77:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  sf(" %s",&a);sf(" %s",&b);
      |                 ^

• Subtask 1: 15 / 15