oj.uz

Submission #376980

# Submission time Handle Problem Language Result Execution time Memory
376980 2021-03-12T13:58:31 Z sinamhdv Necklace (Subtask 1-3) (BOI19_necklace1) C++11
0 / 85
 83 ms 108140 KB 
#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[MAXN][2 * MAXN];
int lcp[MAXN][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(kmp, 0, sizeof(kmp));
	memset(lcp, 0, sizeof(lcp));

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

	FOR(i, 0, n)
	{
		FOR(j, 0, m)
			lcp[i][j] = j - 1;
		FOR(j, 0, m)
		{
			int pos = j - kmp[i][j + n - i + 2] + 1;
			lcp[i][pos] = j;
		}
		FOR(j, 1, m)
			lcp[i][j] = max(lcp[i][j - 1], lcp[i][j]);
		FOR(j, 0, m)
		{
			lcp[i][j] = lcp[i][j] - j + 1;
		}
	}

	FOR(i, 0, n)
	{
		FOR(j, 0, m)
		{
			int l = lcp[i][j];
			int blcp = getblcp(i + l, j - 1);
			if (l + blcp > ans)
			{
				ans = l + blcp;
				sind = i;
				tind = (rev ? m - 1 - (j + l - 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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 108140 KB Output is correct
2 Correct 76 ms 108128 KB Output is correct
3 Correct 83 ms 108140 KB Output is correct
4 Incorrect 73 ms 108140 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 108140 KB Output is correct
2 Correct 76 ms 108128 KB Output is correct
3 Correct 83 ms 108140 KB Output is correct
4 Incorrect 73 ms 108140 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 108140 KB Output is correct
2 Correct 76 ms 108128 KB Output is correct
3 Correct 83 ms 108140 KB Output is correct
4 Incorrect 73 ms 108140 KB Output isn't correct
5 Halted 0 ms 0 KB -