/*
Я русский,
Я иду до конца.
Я русский,
Моя кровь от Отца.
Я русский,
И мне повезло.
Я русский,
Всему миру назло.
Я русский!
*/
//#pragma GCC optimize("O3")'
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <cstdio>
#include <cmath>
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define double long double
#define int long long
using ll = long long;
const int mod = 1e9 + 7;
const int mod9 = 1e9 + 9;
const ll MAXN = 1e6 + 100;
const int MAXB = 8;
const int MAXL = 1e6 + 1e5;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << (#x) << ": " << x << endl;
#else
#define debug(x)
#endif
int bin_pow(int x, int e) {
int c = x, r = 1;
for (; e; e >>= 1, c = c * 1LL * c % mod) {
if (e & 1) r = r * 1LL * c % mod;
}
return r;
}
int rev(int a) {
return bin_pow(a, mod - 2);
}
int make_add(int x, int y) {
if ((ll)x + y >= mod) return x + y - mod;
return x + y;
}
int mul(int x, int y) {
ll p = (ll(x)) * y;
return p % mod;
}
int gcd(int a, int b) {
while (a > 0 && b > 0) {
int c = a;
a = b % a;
b = c;
}
return a + b;
}
vector<int> prefix_function(string s) {
int n = (int)s.length();
vector<int> pi(n);
for (int i = 1; i < n; ++i) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
return pi;
}
int get(string s, string t) {
if (s.size() > t.size()) swap(s, t);
int n = s.size(), m = t.size();
s = s + s;
t = t + t;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
string to_ab;
for (int p = i; p < i + n; p++) to_ab += s[p];
to_ab += '#';
for (int p = j; p < j + m; p++) to_ab += t[p];
vector<int> ab = prefix_function(to_ab);
//for (auto c : ab) cout << c << " ";
//cout << endl;
string to_ba = to_ab;
reverse(to_ba.begin(), to_ba.end());
vector<int> ba = prefix_function(to_ba);
// for (auto c : ba) cout << c << " ";
// cout << endl;
for (int p = n + 1; p <= n + m; p++) {
int cur_add = ab[p];
if (cur_add != p - n) continue;
int pos = n + m + 1 - cur_add - 1;
int may = ba[pos];
ans = max(ans, may + cur_add);
}
}
}
return ans;
}
void solve() {
string s, t;
cin >> s >> t;
int mx1 = get(s, t);
reverse(t.begin(), t.end());
int mx2 = get(s, t);
cout << max(mx1, mx2);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1 - 1 + 1;
// cin >> t;
while (t--) {
solve();
}
}
/*
abcd
dcab
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
436 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
436 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
436 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
