//Be Name Khoda
#include<bits/stdc++.h>
#pragma GCC optmize("Ofast,unroll-loops")
#pragma GCC target ("avx2,tune=native")
using namespace std;
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
const int mxn = 3e3 + 16;
const ll md = 1e9 + 7, md2 = 998244353, p1 = 27, p2 = 31;
ll n, m, q, w, t, sum;
int mid, l, r;
int g[mxn], g2[mxn], f[mxn], f2[mxn], taq[mxn], qat[mxn];
string s, h;
void input() {
cin >> s >> h;
}
inline ll tav(ll a, ll b, ll d) {
ll res = 1;
while(b > 0) {
if(b & 1) res *= a; res %= d;
a *= a; a %= d; b >>= 1;
}
return res;
}
inline void GGL() {
taq[0] = qat[0] = 1;
taq[1] = tav(p1, md - 2, md); qat[1] = tav(p2, md2 - 2, md2);
for(int i = 2; i < mxn; i++) {
taq[i] = 1LL * taq[i - 1] * taq[1] % md;
qat[i] = 1LL * qat[i - 1] * qat[1] % md2;
} return;
}
inline void build_hash() {
n = int(s.size());
q = 0, w = 1;
for(int i = 0; i < n; i++) {
q = q + (1LL * w * (s[i] - 'a')); q %= md;
g[i] = q; w *= p1; w %= md;
} q = 0, w = 1;
for(int i = 0; i < n; i++) {
q = q + (1LL * w * (s[i] - 'a')); q %= md2;
g2[i] = q; w *= p2; w %= md2;
}
return;
}
inline void build_hash2() {
m = int(h.size());
q = 0, w = 1;
for(int i = 0; i < m; i++) {
q = q + (1LL * w * (h[i] - 'a')); q %= md;
f[i] = q; w *= p1; w %= md;
} q = 0, w = 1;
for(int i = 0; i < m; i++) {
q = q + (1LL * w * (h[i] - 'a')); q %= md2;
f2[i] = q; w *= p2; w %= md2;
}
return;
}
inline pii hashG(int lx, int rx) {
if(lx == 0) {
q = g[rx - 1], w = g2[rx - 1];
return make_pair(q, w);
}
q = g[rx - 1] - g[lx - 1]; q %= md; q += md; q %= md;
q = 1LL * q * taq[lx] % md;
w = g2[rx - 1] - g2[lx - 1]; w %= md2; w += md2; w %= md2;
w = 1LL * w * qat[lx] % md2;
return make_pair(q, w);
}
inline pii hashF(int lx, int rx) {
if(lx == 0) {
q = f[rx - 1], w = f2[rx - 1];
return make_pair(q, w);
}
q = f[rx - 1] - f[lx - 1]; q %= md; q += md; q %= md;
q = 1LL * q * taq[lx] % md;
w = f2[rx - 1] - f2[lx - 1]; w %= md2; w += md2; w %= md2;
w = 1LL * w * qat[lx] % md2;
return make_pair(q, w);
}
inline int bs(int a, int b) {
l = 0, r = min(n - a, m - b);
for(int i = 11; i > -1; i--) {
if(l + (1 << i) > r) continue;
if(hashG(a, a + l + (1 << i)) == hashF(b, b + l + (1 << i))) l += (1 << i);
}
return l;
}
inline int bs2(int a, int b) {
l = 0, r = min(1LL * a, m - b - sum);
for(int i = 11; i > -1; i--) {
if(l + (1 << i) > r) continue;
if(hashG(a - (l + (1 << i)), a) == hashF(b + sum, b + sum + l + (1 << i))) l += (1 << i);
}
return l;
}
void solve() {
GGL();
build_hash(); build_hash2();
int ans = 0, st1 = -1, st2 = -1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(m - j < ans) break;
if(s[i] != h[j]) continue;
sum = bs(i, j);
w = bs2(i, j); sum += w;
if(sum > ans) {
st1 = i - w; st2 = j; ans = sum;
}
}
}
reverse(all(h));
build_hash2();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(m - j < ans) break;
if(s[i] != h[j]) continue;
sum = bs(i, j);
w = bs2(i, j); sum += w;
if(sum > ans) {
st1 = i - w; st2 = m - j - sum; ans = sum;
}
}
}
cout << ans << "\n";
cout << st1 << " " << st2 << "\n";
return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
input(), solve();
return 0;
}
Compilation message
necklace.cpp:4: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
4 | #pragma GCC optmize("Ofast,unroll-loops")
|
necklace.cpp: In function 'long long int tav(long long int, long long int, long long int)':
necklace.cpp:32:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
32 | if(b & 1) res *= a; res %= d;
| ^~
necklace.cpp:32:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
32 | if(b & 1) res *= a; res %= d;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 3 |
Partially correct |
3 ms |
332 KB |
Output is partially correct |
| 4 |
Partially correct |
2 ms |
332 KB |
Output is partially correct |
| 5 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 3 |
Partially correct |
3 ms |
332 KB |
Output is partially correct |
| 4 |
Partially correct |
2 ms |
332 KB |
Output is partially correct |
| 5 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 6 |
Partially correct |
10 ms |
352 KB |
Output is partially correct |
| 7 |
Correct |
6 ms |
332 KB |
Output is correct |
| 8 |
Correct |
77 ms |
340 KB |
Output is correct |
| 9 |
Partially correct |
34 ms |
332 KB |
Output is partially correct |
| 10 |
Partially correct |
6 ms |
332 KB |
Output is partially correct |
| 11 |
Partially correct |
6 ms |
332 KB |
Output is partially correct |
| 12 |
Partially correct |
46 ms |
332 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 3 |
Partially correct |
3 ms |
332 KB |
Output is partially correct |
| 4 |
Partially correct |
2 ms |
332 KB |
Output is partially correct |
| 5 |
Partially correct |
1 ms |
332 KB |
Output is partially correct |
| 6 |
Partially correct |
10 ms |
352 KB |
Output is partially correct |
| 7 |
Correct |
6 ms |
332 KB |
Output is correct |
| 8 |
Correct |
77 ms |
340 KB |
Output is correct |
| 9 |
Partially correct |
34 ms |
332 KB |
Output is partially correct |
| 10 |
Partially correct |
6 ms |
332 KB |
Output is partially correct |
| 11 |
Partially correct |
6 ms |
332 KB |
Output is partially correct |
| 12 |
Partially correct |
46 ms |
332 KB |
Output is partially correct |
| 13 |
Partially correct |
1202 ms |
372 KB |
Output is partially correct |
| 14 |
Correct |
480 ms |
384 KB |
Output is correct |
| 15 |
Execution timed out |
1593 ms |
300 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
