제출 #1261078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261078		ebrambill	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	134 ms	35748 KiB

necklace

//In the name of GOD

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

#define f first
#define s second

const int maxN=3e3+5;
int n, m, lps[maxN][maxN], tmp[maxN<<1]={-1};
string s, t, ts;
pair<int, pair<int, int>> ans;

void solve(bool b){
	for (int i=m; i>=1; i--){
		for (int j=i, cur=j-1; j<=n+m+1; j++, cur=j-1){
			while(ts[tmp[cur-i+1]+i]!=ts[j] and tmp[cur-i+1]>=0) cur=tmp[cur-i+1]+i-1;
			tmp[j-i+1]=tmp[cur-i+1]+1;
			if(j>m+1) lps[i][j-m-1]=tmp[j-i+1];
		}
	}

	for (int i=1; i<=m; i++)
		for (int j=1; j<=n; j++)
			if(lps[i][j]+lps[i+lps[i][j]][j-lps[i][j]]>ans.f) ans={lps[i][j]+lps[i+lps[i][j]][j-lps[i][j]], {i-1, (!b ? j-lps[i][j] : n-j)}};
}

int main(){
	cin >>s >>t;
	n=s.size(), m=t.size();
	ts='.'+t+'.'+s;
	solve(0);
	reverse(s.begin(), s.end());
	ts='.'+t+'.'+s;
	solve(1);
	cout <<ans.f <<endl <<ans.s.s <<' ' <<ans.s.f;
}

• Subtask 1: 0 / 15