// Thanks to : TVA
// Strycks, L3, PAD, TVT, NGUYEN^2, Whisper
// My friends...
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define plli pair<ll, int>
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define bit(mask, i) ((mask >> i) & 1)
#define fi first
#define se second
#define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
#define Ford(i, b, a) for(int i = (b) ; i >= (a) ; --i)
#define FILE freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout);
#define int long long
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using str = string;
using ld = long double;
using ull = unsigned long long;
using htype = unsigned long long;
template <class T> bool ckmin(T &a, const T &b) {return (a > b ? a = b, true : false); };
template <class T> bool ckmax(T &a, const T &b) {return (a < b ? a = b, true : false); };
template <class T> void compress(vector <T> &a) {sort(all(a)); a.resize(unique(all(a)) - a.begin()); };
template <class T> int getcom(vector<T> &a, T val) {return lower_bound(all(a), val) - a.begin() + 1; };
const ll mod = 1e9 + 7; /// MOD CHANGED
ll add(ll x, ll y){
return (x + y) % mod;
}
ll sub(ll x, ll y){
return ((x - y) % mod + mod) % mod;
}
ll mul(ll x, ll y){
return (x * y) % mod;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
const char MOVE[] = {'U', 'L', 'R', 'D'};
const ll INFll = 0x3f3f3f3f3f3f3f3f;
const int INFin = 0x3f3f3f3f;
const int maxn = 3e2 + 5; /// MAXN CHANGED
const int maxv = 1e6 + 5; /// MAXV CHANGED
// s[0, n - 1]
vector <int> Zfun(str s){
int n = s.size();
vector <int> z(n, 0);
for(int l = 0, r = 0, i = 1 ; i < n ; ++i){
if(i <= r) z[i] = min(z[i - l], r - i + 1);
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
if(i + z[i] - 1 > r){
l = i;
r = i + z[i] - 1;
}
}
return z;
}
vector <int> kmp(str s){
int n = s.size();
vector <int> pi(n, 0);
for(int i = 1 ; i < n ; ++i){
int len = pi[i - 1];
while(len > 0 && s[i] != s[len]) len = pi[len - 1];
pi[i] = len + (s[i] == s[len]);
}
return pi;
}
vector < vector<int> > autu(str s){
vector <int> pi = kmp(s);
int n = s.size() - 1;
vector < vector<int> > nxt(n + 1, vector<int>(26, 0));
For(len, 0, n){
For(c, 0, 25){
if(s[len] == (c + 'a')) nxt[len][c] = len + 1;
else if(len > 0) nxt[len][c] = nxt[pi[len - 1]][c];
}
}
return nxt;
}
#define piii pair<int, pii>
int lef[maxn][maxn], rig[maxn][maxn];
piii cal(str a, str b){
str cur = "";
Ford(i, a.size() - 1, 0){
if(i != a.size()) cur = a[i] + cur;
vector <int> pi = kmp(cur + '%' + b);
For(j, 0, b.size() - 1){
lef[j][i] = pi[cur.size() + 1 + j];
}
}
cur = "";
Ford(i, b.size() - 1, 0){
if(i != b.size()) cur = b[i] + cur;
vector <int> pi = kmp(cur + '%' + a);
For(j, 0, a.size() - 1){
rig[i][j] = pi[cur.size() + 1 + j];
}
}
piii ans = {0, {0, 0}};
For(i, 0, b.size()){
For(j, 0, a.size()){
int l = 0, r = 0;
if(i > 0) l = lef[i - 1][j];
if(j > 0) r = rig[i][j - 1];
if(ans.fi < l + r){
ans.fi = l + r;
ans.se = {j - r, i - l};
}
}
}
return ans;
}
signed main(){
fast
#define name "Anya"
// FILE
str a, b; cin >> a >> b;
piii ans = cal(a, b);
reverse(all(b));
ckmax(ans, cal(a, b));
cout << ans.fi << '\n';
cout << ans.se.fi << " " << ans.se.se;
}
Compilation message
necklace.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > cal(str, str)':
necklace.cpp:114:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | if(i != a.size()) cur = a[i] + cur;
| ~~^~~~~~~~~~~
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
| ^
necklace.cpp:116:9: note: in expansion of macro 'For'
116 | For(j, 0, b.size() - 1){
| ^~~
necklace.cpp:124:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | if(i != b.size()) cur = b[i] + cur;
| ~~^~~~~~~~~~~
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
| ^
necklace.cpp:126:9: note: in expansion of macro 'For'
126 | For(j, 0, a.size() - 1){
| ^~~
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
| ^
necklace.cpp:133:5: note: in expansion of macro 'For'
133 | For(i, 0, b.size()){
| ^~~
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
| ^
necklace.cpp:134:9: note: in expansion of macro 'For'
134 | For(j, 0, a.size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
2128 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
