#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int M = 1e9 + 9;
const int B = 1854;
int add(int a, int b) {
a += b;
if (a >= M) a -= M;
if (a < 0) a += M;
return a;
}
int mul(int a, int b) {
return 1ll*a*b%M;
}
const int N = 105;
int n, m, h[N], h1[N], h2[N], pw[N];
string s, t;
int H(int l, int r) {
return add(h[r], -mul(h[l], pw[r-l]));
}
int H1(int l, int r) {
return add(h1[r], -mul(h1[l], pw[r-l]));
}
int H2(int l, int r) {
return add(h2[l], -mul(h2[r], pw[r-l]));
}
void solve() {
cin >> s >> t;
n = s.size();
m = t.size();
pw[0] = 1;
for (int i = 1; i < N; i++) {
pw[i] = mul(pw[i-1], B);
}
for (int i = 1; i <= n; i++) {
h[i] = add(mul(h[i-1], B), s[i]);
}
for (int i = 1; i <= m; i++) {
h1[i] = add(mul(h1[i-1], B), t[i]);
}
for (int i = m-1; i >= 0; i--) {
h2[i] = add(mul(h2[i+1], B), t[i]);
}
int ans = 0;
for (int l1 = 0; l1 < n; l1++) {
for (int r1 = l1+1; r1 <= n; r1++) {
int len = r1-l1;
int tmp = H(l1, r1);
for (int l2 = 0; l2 <= m-len; l2++) {
int r2 = l2 + len;
for (int p = l2; p < r2; p++) {
int tmp1 = add(H1(l2, p), mul(H1(p, r2), pw[p-l2]));
int tmp2 = add(H2(p, r2), mul(H2(l2, p), pw[r2-p]));
if (tmp == tmp1 || tmp == tmp2) {
ans = max(ans, len);
}
}
}
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1584 ms |
324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
