oj.uz

Submission #376974

# Submission time Handle Problem Language Result Execution time Memory
376974 2021-03-12T13:41:49 Z sinamhdv Necklace (Subtask 1-3) (BOI19_necklace1) C++11
25 / 85
 64 ms 72256 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];

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;
		// compare s[x, x + mid - 1] with t[y, y + mid - 1]
		if (kmp[x][y + mid - 1 + n - x + 2] >= mid)
			l = mid;
		else
			r = mid;
	}
	return l;
}

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

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

	solve(0);

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 72172 KB Output is correct
2 Correct 48 ms 72256 KB Output is correct
3 Correct 49 ms 72172 KB Output is correct
4 Correct 49 ms 72172 KB Output is correct
5 Correct 49 ms 72172 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 72172 KB Output is correct
2 Correct 48 ms 72256 KB Output is correct
3 Correct 49 ms 72172 KB Output is correct
4 Correct 49 ms 72172 KB Output is correct
5 Correct 49 ms 72172 KB Output is correct
6 Correct 61 ms 72172 KB Output is correct
7 Correct 53 ms 72172 KB Output is correct
8 Correct 64 ms 72172 KB Output is correct
9 Incorrect 59 ms 72192 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 72172 KB Output is correct
2 Correct 48 ms 72256 KB Output is correct
3 Correct 49 ms 72172 KB Output is correct
4 Correct 49 ms 72172 KB Output is correct
5 Correct 49 ms 72172 KB Output is correct
6 Correct 61 ms 72172 KB Output is correct
7 Correct 53 ms 72172 KB Output is correct
8 Correct 64 ms 72172 KB Output is correct
9 Incorrect 59 ms 72192 KB Output isn't correct
10 Halted 0 ms 0 KB -