Submission #376971

#TimeUsernameProblemLanguageResultExecution timeMemory
376971sinamhdvNecklace (Subtask 1-3) (BOI19_necklace1)C++11
45 / 85
1587 ms72428 KiB
#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 sph[MAXN], tph[MAXN];
int pw[MAXN];
int ans;
int sind, tind;

inline void prehash(const string &s, int *ph)
{
	FOR(i, 1, (int)s.size() + 1)
	{
		ph[i] = ((ll)ph[i - 1] * prm + s[i - 1]) % mod;
	}
}

inline ll gethash(int *ph, int l, int r)
{
	int res = ph[r + 1] - (ll)ph[l] * pw[r - l + 1] % mod;
	return (mod + res) % mod;
}

inline int getlcp(int x, int y)
{
	if (s[x] != t[y]) return 0;
	int l = 1;
	int r = min(n - x, m - y) + 1;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (gethash(sph, x, x + mid - 1) == gethash(tph, y, y + mid - 1))
			l = mid;
		else
			r = mid;
	}
	return l;
}

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

void solve(bool rev)
{
	memset(sph, 0, sizeof(sph));
	memset(tph, 0, sizeof(tph));
	prehash(s, sph);
	prehash(t, tph);
	memset(kmp, 0, sizeof(kmp));

	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, 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();

	pw[0] = 1;
	FOR(i, 1, MAXN)
	{
		pw[i] = (ll)pw[i - 1] * prm % mod;
	}

	solve(0);

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

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...