//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;
ll 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] = taq[i - 1] * taq[1] % md;
qat[i] = 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 l, int r) {
if(l == 0) {
q = g[r - 1], w = g2[r - 1];
return make_pair(q, w);
}
q = g[r - 1] - g[l - 1]; q %= md; q += md; q %= md;
q = 1LL * q * taq[l] % md;
w = g2[r - 1] - g2[l - 1]; w %= md2; w += md2; w %= md2;
w = 1LL * w * qat[l] % md2;
return make_pair(q, w);
}
inline pii hashF(int l, int r) {
if(l == 0) {
q = f[r - 1], w = f2[r - 1];
return make_pair(q, w);
}
q = f[r - 1] - f[l - 1]; q %= md; q += md; q %= md;
q = 1LL * q * taq[l] % md;
w = f2[r - 1] - f2[l - 1]; w %= md2; w += md2; w %= md2;
w = 1LL * w * qat[l] % md2;
return make_pair(q, w);
}
inline int bs(int a, int b) {
int mid, l, r;
l = 1, r = min(n - a, m - b) + 1;
while(l < r) {
if(r - l == 1) break;
mid = (l + r) >> 1;
if(hashG(a, a + mid) == hashF(b, b + mid)) {
l = mid;
} else {
r = mid;
}
}
return l;
}
inline int bs2(int a, int b) {
int mid, l, r;
l = 0, r = min(1LL * a, m - b - sum) + 1;
while(l < r) {
if(r - l == 1) break;
mid = (l + r) >> 1;
if(hashG(a - mid, a) == hashF(b + sum, b + sum + mid)) {
l = mid;
} else {
r = mid;
}
}
return l;
}
void solve() {
GGL();
build_hash(); build_hash2();
t = min(n, m);
ll ans = 0, st1 = -1, st2 = -1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
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(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:31:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
31 | if(b & 1) res *= a; res %= d;
| ^~
necklace.cpp:31:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
31 | if(b & 1) res *= a; res %= d;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
392 KB |
Output is correct |
| 2 |
Partially correct |
2 ms |
336 KB |
Output is partially correct |
| 3 |
Correct |
3 ms |
336 KB |
Output is correct |
| 4 |
Partially correct |
2 ms |
336 KB |
Output is partially correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
392 KB |
Output is correct |
| 2 |
Partially correct |
2 ms |
336 KB |
Output is partially correct |
| 3 |
Correct |
3 ms |
336 KB |
Output is correct |
| 4 |
Partially correct |
2 ms |
336 KB |
Output is partially correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
90 ms |
372 KB |
Output is correct |
| 7 |
Partially correct |
31 ms |
336 KB |
Output is partially correct |
| 8 |
Correct |
67 ms |
336 KB |
Output is correct |
| 9 |
Partially correct |
40 ms |
368 KB |
Output is partially correct |
| 10 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 11 |
Partially correct |
6 ms |
324 KB |
Output is partially correct |
| 12 |
Partially correct |
51 ms |
368 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
392 KB |
Output is correct |
| 2 |
Partially correct |
2 ms |
336 KB |
Output is partially correct |
| 3 |
Correct |
3 ms |
336 KB |
Output is correct |
| 4 |
Partially correct |
2 ms |
336 KB |
Output is partially correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
90 ms |
372 KB |
Output is correct |
| 7 |
Partially correct |
31 ms |
336 KB |
Output is partially correct |
| 8 |
Correct |
67 ms |
336 KB |
Output is correct |
| 9 |
Partially correct |
40 ms |
368 KB |
Output is partially correct |
| 10 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 11 |
Partially correct |
6 ms |
324 KB |
Output is partially correct |
| 12 |
Partially correct |
51 ms |
368 KB |
Output is partially correct |
| 13 |
Execution timed out |
1551 ms |
448 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
