// 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 = 998244353; /// 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 = 3e3 + 5; /// MAXN CHANGED
const int maxv = 1e6 + 5; /// MAXV CHANGED
vector <int> zfun(str s){
int n = s.size();
vector <int> z(n, 0);
int l = 0, r = 0;
For(i, 1, n - 1){
if(l <= i && i <= r) z[i] = min(r - i + 1, z[i - l]);
while(i + z[i] < n && s[i + z[i]] == s[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(i, 1, n - 1){
int k = pi[i - 1];
while(k > 0 && s[k] != s[i]) k = pi[k - 1];
if(s[k] == s[i]) ++k;
pi[i] = k;
}
return pi;
}
vector <vector<int>> automa(str s){
int n = s.size();
s = s + '#';
vector <int> pi = kmp(s);
vector <vector<int>> nxt(n + 1, vector<int>(26, 0));
For(x, 0, n){
For(c, 0, 25){
if(x > 0 && s[x] != c + 'a') nxt[x][c] = nxt[pi[x - 1]][c];
else nxt[x][c] = x + (s[x] == c + 'a');
}
}
return nxt;
}
str a, b;
int n, m;
void init(){
cin >> a >> b;
n = a.size();
m = b.size() - 1;
}
str rev(str a){
reverse(all(a));
return a;
}
struct uwu{int mustlen, val; };
int fen[maxn][maxn];
void upd(int fen[], int x, int val){
assert(x >= 0);
if(x == 0) return;
for(; x <= n ; x += (x & -x)) ckmax(fen[x], val);
}
int get(int fen[], int x){
int ans = 0;
for(; x > 0 ; x -= (x & -x)) ckmax(ans, fen[x]);
return ans;
}
void precal(str a, str b, int cnt){
int n = a.size();
vector <int> z = zfun(a + '#' + b);
For(i, n + 1, z.size() - 1){
upd(fen[m - (i - n - 1)], n - z[i], n);
}
}
void precal1(str a, str b){
str tmp = b;
reverse(all(tmp));
int cnt = 0;
while(a.size()){
precal(rev(a), tmp, ++cnt);
a.pop_back();
}
}
pair<int, pii> cal(str a, str b, int aps){
pair<int, pii> ans = {0, {0, 0}};
int n = a.size();
vector <int> z = zfun(a + '#' + b);
For(i, n + 1, z.size() - 1){
ckmax(ans, {z[i], {i - n - 1, i - n - 2 + z[i]}});
if(i == n + 1) continue;
int len = get(fen[i - n - 2], z[i] + aps);
ckmax(ans, {len - aps, {i - n - 1, i - n - 2 + z[i]}});
}
return ans;
}
pair<int, pii> solve(str a, str b){
pair<int, pii> ans = {0, {0, 0}};
precal1(a, b);
For(aps, 0, n - 1){
ckmax(ans, cal(a, b, aps));
a.erase(0, 1);
}
memset(fen, 0, sizeof(fen));
return ans;
}
void trace(str a, pair<int, pii> ans, bool type){
cout << ans.fi << '\n';
int pos = ans.se.se - ans.fi + 1;
str tmp = "";
For(i, ans.se.fi, ans.se.se) tmp += b[i];
For(i, pos, ans.se.fi - 1) tmp += b[i];
int res = (int)a.find(tmp);
assert(res != -1);
if(type) res = n - res - ans.fi;
cout << res << " " << pos;
}
void get(){
pair<int, pii> ans = solve(a, b);
pair<int, pii> ans2 = solve(rev(a), b);
if(ans > ans2) trace(a, ans, 0);
else trace(rev(a), ans2, 1);
}
signed main(){
fast
#define name "Anya"
// FILE
init();
get();
}
Compilation message
necklace.cpp: In function 'void precal(str, str, long long int)':
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
| ^
necklace.cpp:137:5: note: in expansion of macro 'For'
137 | For(i, n + 1, z.size() - 1){
| ^~~
necklace.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > cal(str, str, long long int)':
necklace.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
| ^
necklace.cpp:161:5: note: in expansion of macro 'For'
161 | For(i, n + 1, z.size() - 1){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
501 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
