#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define what(x) cout << (#x) << " -> " << x << '\n';
#define cno cout << "NO" \
<< "\n"
#define cy cout << "YES" \
<< "\n"
#define c1 cout << "-1" << '\n'
#define pb push_back
#define ff first
#define ss second
#define sz size()
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
const ll N = 1000005;
const ll mod = 1000000007;
ll n, m, x, y, z, l, r, d, q, mx, mn, sum, temp;
ll a[N];
vector<int> prefix_function(string s, int start)
{
int n = (int)s.length();
vector<int> pi(n), ans;
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;
}
for (int i = start; i < n; i++)
ans.pb(pi[i]);
return ans;
}
vector<int> suffix_function(string s, int start)
{
int n = (int)s.length();
vector<int> pi(n), ans;
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;
}
for (int i = start; i < n; i++)
ans.pb(pi[i]);
reverse(ans.begin(), ans.end());
return ans;
}
int solve(string s, string t)
{
string te;
n = s.sz;
m = t.sz;
s += s;
t += t;
te = t;
reverse(te.begin(), te.end());
pair<int, int> ans{-1, -1};
vector<int> z, p;
int mx = 0;
for (int i = 0; i < n; i++)
{
// what(i);
string r = s.substr(i, n), f;
f = r;
r += '#';
r += t;
reverse(f.begin(), f.end());
f += '#';
f += te;
// cout << r << ' ' << f << endl;
z = suffix_function(f, n + 1), p = prefix_function(r, n + 1);
for (int i = 0; i < m; i++)
{
mx = max(min(p[i] + z[i + 1], int(m)), mx);
// cout << p[i] << ' ' << z[i + 1] << endl;
}
}
return mx;
}
int main()
{
IOS int testcases = 1;
// cin >> testcases;
while (testcases--)
{
string s, t;
string se, te;
cin >> s >> t;
n = s.sz;
m = t.sz;
se = s;
te = t;
reverse(se.begin(), se.end());
cout << max(solve(se, te), solve(s, t));
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
467 ms |
604 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
