oj.uz

답안 #722145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722145 2023-04-11T12:51:03 Z jamezzz Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 194 ms 340 KB 
#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

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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 5 ms 304 KB Output is correct
7 Correct 3 ms 300 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 300 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 3 ms 212 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 5 ms 304 KB Output is correct
7 Correct 3 ms 300 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 300 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 3 ms 212 KB Output is correct
13 Correct 175 ms 340 KB Output is correct
14 Correct 145 ms 340 KB Output is correct
15 Correct 194 ms 324 KB Output is correct
16 Correct 147 ms 340 KB Output is correct
17 Correct 101 ms 340 KB Output is correct
18 Correct 106 ms 340 KB Output is correct
19 Correct 126 ms 340 KB Output is correct
20 Correct 168 ms 328 KB Output is correct
21 Correct 153 ms 340 KB Output is correct