/*
Я русский,
Я иду до конца.
Я русский,
Моя кровь от Отца.
Я русский,
И мне повезло.
Я русский,
Всему миру назло.
Я русский!
*/
//#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;
}
const int base = 61;
struct hashes {
vector<int> power;
vector<int> pref;
void init(string s, int m) {
int n = s.size();
pref = vector<int>(n + 1);
power = vector<int>(n + 1);
power[0] = 1;
for (int i = 0; i < n; i++) {
pref[i + 1] = (pref[i] * base + s[i] - 96) % m;
power[i + 1] = (power[i] * base) % m;
}
}
int get(int i, int j, int m) {
int ans = (pref[j] - (pref[i] * (power[j - i]) % m) + m) % m;
return ans;
}
};
int get_st(string s, string t) {
int n = s.size(), m = t.size();
set<pair<int, int> > all_hash_s;
for (int i = 0; i < n; i++) {
string add;
for (int j = i; j < n; j++) {
add += s[j];
string cadd = add;
add = add + add;
hashes m7, m9;
m7.init(add, mod);
m9.init(add, mod9);
for (int p = 0; p < cadd.size(); p++) {
int l = p, r = p + cadd.size();
int hash7 = m7.get(l, r, mod), hash9 = m9.get(l, r, mod9);
all_hash_s.insert({ hash7, hash9 });
}
add = cadd;
}
}
int mx = 0;
for (int i = 0; i < m; i++) {
string add;
for (int j = i; j < m; j++) {
add += t[j];
string cadd = add;
add = add + add;
hashes m7, m9;
m7.init(add, mod);
m9.init(add, mod9);
for (int p = 0; p < cadd.size(); p++) {
int l = p, r = p + cadd.size();
int hash7 = m7.get(l, r, mod), hash9 = m9.get(l, r, mod9);
if (all_hash_s.count({ hash7,hash9 })) {
mx = max(mx, j - i + 1);
break;
}
}
add = cadd;
}
}
return mx;
}
int stupid(string s, string t) {
int mx1 = get_st(s, t);
reverse(t.begin(), t.end());
int mx2 = get_st(s, t);
return max(mx1, mx2);
}
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) {
int n = s.size(), m = t.size();
vector<vector<int> > pre_prefix_func;
for (int i = 0; i <= m; i++) {
string cur;
for (int j = 0; j < n; j++) cur += s[j];
cur += '#';
for (int j = 0; j < i; j++) {
cur += t[j];
}
reverse(cur.begin(), cur.end());
vector<int> p = prefix_function(cur);
pre_prefix_func.push_back(p);
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 1; j++) {
string to_ab;
for (int p = i; p < n; p++) to_ab += s[p];
to_ab += '#';
for (int p = 0; p < m; p++) to_ab += t[p];
vector<int> ab = prefix_function(to_ab);
int sz = ab.size();
int what_to_n = n - i;
for (int p = what_to_n + 1; p < sz; p++) {
int cur_add = ab[p];
//if (cur_add != p - what_to_n) continue;
int ind = p - what_to_n - cur_add;
int pos = cur_add + i + 1;
pos = ind + 1 + n - pos;
int may = pre_prefix_func[ind][pos];
ans = max(ans, may + cur_add);
}
}
}
return ans;
}
int clever(string s, string t) {
int mx1 = get(s, t);
reverse(t.begin(), t.end());
int mx2 = get(s, t);
return max(mx1, mx2);
}
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);
}
void gen() {
string s, t;
int n = rand() % 5 + 1, m = rand() % 5 + 1;
for (int i = 0; i < n; i++) {
int r = rand() % 3;
s += (char)(r + 97);
}
for (int i = 0; i < m; i++) {
int r = rand() % 3;
t += (char)(r + 97);
}
int st = stupid(s, t);
int cl = clever(s, t);
if (st != cl) {
cout << s << " " << t << endl;
cout << st << " " << cl << endl;
exit(0);
}
}
int num = 0;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1 - 1 + 1;
/*
while (true) {
debug(num++);
gen();
}
*/
// cin >> t;
while (t--) {
solve();
}
}
/*
acccb
ccabc
*/
Compilation message
necklace.cpp: In function 'int get_st(std::string, std::string)':
necklace.cpp:96:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int p = 0; p < cadd.size(); p++) {
| ~~^~~~~~~~~~~~~
necklace.cpp:114:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int p = 0; p < cadd.size(); p++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
