#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define m_p make_pair
#define vec vector
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pw(x) (1LL<<x)
#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker,"/stack:20000000")
//#pragma GCC target("sse,sse2,sse3,sse3,ssse3,abm,avx,avx2,tune=native")
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
template<class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> bool umax(T &a, T b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a, T b){return (a>b?a=b,1:0);}
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef unsigned long long ull;
const int N=3e3+2;
int dp1[N][N];
int dp2[N][N];
int func[2*N];
void calc(int *pf,const string &s){
for(int i=1;i<sz(s);i++){
int j=pf[i-1];
while(j>0 && s[j]!=s[i]){
j=pf[j-1];
}
pf[i]=j;
pf[i]+=(s[i]==s[j]);
}
}
signed main(){
fast_ioi;
string s,t;
cin>>s>>t;
int ans=-1;
int f=-1,se=-1;
int n=sz(s),m=sz(t);
{
/// заканчивая в j and staring at i
for(int i=0;i<n;i++){
string lel=s.substr(i,n-1)+'#'+t;
int w=(n-1-i+1)+1;
calc(func,lel);
for(int j=0;j<m;j++){
dp1[i][j]=func[j+w];
}
}
/// заканчивая в i and staring at j
for(int j=0;j<m;j++){
string lel=t.substr(j,m-1)+'#'+s;
int w=(m-1-j+1)+1;
calc(func,lel);
for(int i=0;i<n;i++){
dp2[i][j]=func[i+w];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int st1=i-(i?dp2[i-1][j]:0),st2=j-(j?dp1[i][j-1]:0);
int dl=(i?dp2[i-1][j]:0)+(j?dp1[i][j-1]:0);
if(umax(ans,dl)){
f=st1,se=st2;
}
}
}
}
// {
// reverse(all(s));
// /// заканчивая в j and staring at i
// for(int i=0;i<n;i++){
// string lel=s.substr(i,n-1)+'#'+t;
// int w=(n-i)+1;
// calc(func,lel);
// for(int j=0;j<m;j++){
// dp1[i][j]=func[j+w];
// }
// }
// /// заканчивая в i and staring at j
// for(int j=0;j<m;j++){
// string lel=t.substr(j,m-1)+'#'+s;
// int w=(m-j)+1;
// calc(func,lel);
// for(int i=0;i<n;i++){
// dp2[i][j]=func[i+w];
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// int st1=i+(j?dp1[i][j-1]-1:0),st2=j-(j?dp1[i][j-1]:0);
// int dl=(i?dp2[i-1][j]:0)+(j?dp1[i][j-1]:0);
//// st1=n-st1-1;
// if(umax(ans,dl)){
// f=st1,se=st2;
//
// }
//// debug()<<imie(s)imie(t)imie(i)imie(j)imie(dp1[i][j])imie(dp2[i][j]);
//// print(i);print(j);print()
// }
// }
// reverse(all(s));
// }
//
{
reverse(all(t));
/// заканчивая в j and staring at i
for(int i=0;i<n;i++){
string lel=s.substr(i,n-1)+'#'+t;
int w=(n-i)+1;
calc(func,lel);
for(int j=0;j<m;j++){
dp1[i][j]=func[j+w];
}
}
/// заканчивая в i and staring at j
for(int j=0;j<m;j++){
string lel=t.substr(j,m-1)+'#'+s;
int w=(m-j)+1;
calc(func,lel);
for(int i=0;i<n;i++){
dp2[i][j]=func[i+w];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int st1=i-(i?dp2[i-1][j]:0),st2=j+(i?dp2[i-1][j]-1:0);
int dl=(i?dp2[i-1][j]:0)+(j?dp1[i][j-1]:0);
st2=m-st2-1;
if(umax(ans,dl)){
f=st1,se=st2;
// debug()<<imie(j)imie(s)imie(t)imie(i?dp2[i-1][j]:0)imie((j?dp1[i][j-1]:0));
}
}
}
reverse(all(t));
}
assert(ans!=-1);
cout<<ans<<endl<<f<<' '<<se;
return 0;
}
/*
zxyabcd
ztcdabxy
yxbadctz
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
2 ms |
972 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
2 ms |
972 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
15 ms |
4812 KB |
Output is correct |
| 7 |
Correct |
11 ms |
4816 KB |
Output is correct |
| 8 |
Correct |
11 ms |
4552 KB |
Output is correct |
| 9 |
Correct |
11 ms |
4632 KB |
Output is correct |
| 10 |
Correct |
10 ms |
4788 KB |
Output is correct |
| 11 |
Correct |
11 ms |
4760 KB |
Output is correct |
| 12 |
Correct |
11 ms |
4552 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
2 ms |
972 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
15 ms |
4812 KB |
Output is correct |
| 7 |
Correct |
11 ms |
4816 KB |
Output is correct |
| 8 |
Correct |
11 ms |
4552 KB |
Output is correct |
| 9 |
Correct |
11 ms |
4632 KB |
Output is correct |
| 10 |
Correct |
10 ms |
4788 KB |
Output is correct |
| 11 |
Correct |
11 ms |
4760 KB |
Output is correct |
| 12 |
Correct |
11 ms |
4552 KB |
Output is correct |
| 13 |
Correct |
658 ms |
71028 KB |
Output is correct |
| 14 |
Correct |
605 ms |
70984 KB |
Output is correct |
| 15 |
Correct |
661 ms |
68384 KB |
Output is correct |
| 16 |
Correct |
624 ms |
70660 KB |
Output is correct |
| 17 |
Correct |
564 ms |
69628 KB |
Output is correct |
| 18 |
Correct |
573 ms |
70740 KB |
Output is correct |
| 19 |
Correct |
593 ms |
70468 KB |
Output is correct |
| 20 |
Correct |
608 ms |
69700 KB |
Output is correct |
| 21 |
Correct |
622 ms |
70080 KB |
Output is correct |
