제출 #376982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376982		sinamhdv	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	45 / 85	1164 ms	73068 KiB

necklace

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
const int prm = 727;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 3030
#define LOGN 22

string s, t;
int n, m;
int ans;
int sind, tind;
int rnk[LOGN][2 * MAXN];
pair<pii, int> order[2 * MAXN];

inline int getlcp(int x, int y)
{
	int fr = x;
	for (int i = LOGN - 1; i >= 0; i--)
	{
		if (rnk[i][x] == rnk[i][y])
		{
			x += (1 << i);
			y += (1 << i);
		}
	}
	return x - fr;
}

int kmp[MAXN][2 * MAXN];

inline int getblcp(int x, int y)
{
	if (x >= n || y < 0) return 0;
	return kmp[x][y + n - x + 2];
}


inline void prekmp(const string &s, int *pre)
{
	int cur = 0;
	FOR(i, 1, (int)s.size())
	{
		while (cur > 0 && s[i] != s[cur])
		{
			cur = pre[cur];
		}
		if (s[i] == s[cur])
			cur++;
		pre[i + 1] = cur;
	}
}

inline void sufarr(const string &s)
{
	int n = s.size();
	FOR(i, 0, n)
	{
		rnk[0][i] = (int)s[i];
	}
	FOR(i, 1, LOGN)
	{
		FOR(j, 0, n)
		{
			pii &p = order[j].fr;
			p.fr = rnk[i - 1][j];
			if (j + (1 << (i - 1)) >= n)
			{
				p.sc = -1;
			}
			else
			{
				p.sc = rnk[i - 1][j + (1 << (i - 1))];
			}
			order[j].sc = j;
		}
		sort(order, order + n);
		FOR(j, 0, n)
		{
			if (j > 0 && order[j].fr == order[j - 1].fr)
			{
				rnk[i][order[j].sc] = rnk[i][order[j - 1].sc];
			}
			else
			{
				rnk[i][order[j].sc] = j;
			}
		}
	}
}

void solve(bool rev)
{
	memset(kmp, 0, sizeof(kmp));
	memset(rnk, 0, sizeof(rnk));
	FOR(i, 0, 2 * MAXN)
		order[i] = {{0, 0}, 0};

	string nw = s + '#' + t;
	sufarr(nw);

	FOR(i, 0, n)
	{
		string tmp = s.substr(i) + '#' + t;
		prekmp(tmp, kmp[i]);
	}

	FOR(i, 0, n)
	{
		FOR(j, 0, m)
		{
			int lcp = getlcp(i, n + 1 + j);
			int blcp = getblcp(i + lcp, j - 1);
			if (lcp + blcp > ans)
			{
				ans = lcp + blcp;
				sind = i;
				tind = (rev ? m - 1 - (j + lcp - 1) : j - blcp);
			}
		}
	}
}

int32_t main(void)
{
	fast_io;
	cin >> s >> t;
	n = s.size();
	m = t.size();

	solve(0);
	
	reverse(all(t));
	solve(1);
	
	cout << ans << endl;
	cout << sind << ' ' << tind << endl;
	return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 40