Submission #376995

#	Time	Username	Problem	Language	Result	Execution time	Memory
376995		sinamhdv	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	85 / 85	502 ms	144364 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

string s, t;
int n, m;
int ans;
int sind, tind;
int kmp[2][MAXN][2 * MAXN];

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;
	}
}

void solve(bool rev)
{
	memset(kmp, 0, sizeof(kmp));

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

	FOR(i, 0, n)
	{
		FOR(j, 0, m)
		{
			int l = kmp[1][j][i + m - j + 2];
			int r = (j == 0 || i == n - 1 ? 0 : kmp[0][i + 1][j - 1 + n - (i + 1) + 2]);
			if (l + r > ans)
			{
				ans = l + r;
				sind = i - l + 1;
				tind = (!rev ? j - r : m - 1 - (j + l - 1));
			}
		}
	}
}

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: 40 / 40