#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long int;
using ll = long long int;
bool check(string s, string t){
string ot = s + s;
for(int i=0; i<s.size(); i++) if(ot.substr(i,s.size()) == t) return true;
reverse(s.begin(),s.end());
ot = s + s;
for(int i=0; i<s.size(); i++) if(ot.substr(i,s.size()) == t) return true;
return false;
}
int brute(string & s, string & t){
for(int tam=min(s.size(),t.size()); tam>0; tam--){
for(int i=0; i<=s.size()-tam; i++){
for(int j=0; j<=t.size()-tam; j++){
// cout << s.substr(i,tam) << ' ' << t.substr(j,tam) << '\n';
if(check(s.substr(i,tam),t.substr(j,tam))) {
cout << s.substr(i,tam) << ' ' << t.substr(j,tam) << '\n';
cout << "s e t " << i << ' ' << j << '\n';
return tam;
}
}
}
}
return 0;
}
const int MAX = (int) 3e3 + 10;
int bst_y[MAX],bst_x[MAX];
int p[MAX];
struct info{
int tam, bs,bt;
bool operator <(const info & ot)const{
return tam < ot.tam;
}
};
void set_y(string s, string t){
reverse(s.begin(), s.end()), reverse(t.begin(), t.end());
string str = s + "#" + t;
p[0] = 0;
for(int i=1; i<str.size(); i++){
int j = p[i-1];
while(j != 0 && str[i] != str[j]) j = p[j-1];
if(str[i] == str[j]) j++;
p[i] = j;
}
int id = 0;
for(int i=str.size()-1; str[i] != '#'; i--,id++) bst_y[id] = p[i];
}
void set_x(string s, string t){
string str = s + "#" + t;
p[0] = 0;
for(int i=1; i<str.size(); i++){
int j = p[i-1];
while(j != 0 && str[i] != str[j]) j = p[j-1];
if(str[i] == str[j]) j++;
p[i] = j;
}
int id = 0;
for(int i= s.size()+1; i<str.size(); i++,id++) bst_x[id] = p[i];
}
void test(){
string s,t;
cin >> s >> t;
// escolhe um ponto medio de S
// yyyy|xxxx -> escolho um ponto fixo desse em S
// xxxx|yyyy -> itero nos possiveis pontos dessem em T,
/*
Pro y: maior sufixo antes da | de S que da match com o maior prefixo depois da | de T, mas desse jeito pra fazer KMP teria que ser o prefixo de S, pq o prefixo
depois da barra de T vai estar variando, mas dai eh so da reverse na substring de S antes da barra e na string de T inteira e dai fazer o KMP que vai ser o maior
prefixo de S (o prefixo vai comecar de tras pra frente a partir da barra) com o maior sufixo de um ponto, dai eu vou ter p[i] e dai eu vou guardar em i - p[i]+1
que nessa posicao eu tenho um match de tamanho p[i].
Pro x: maior prefixo depois da | de S que da match com o maior sufixo antes da | de T, dai eh so fazer KMP.
*/
if(s == t){
cout << s.size() << '\n';
cout << 0 << ' ' << 0 << '\n';
return;
}
info ans = {-1,-1,-1};
for(int i=0; i<s.size()-1; i++){
set_y(s.substr(0,i+1),t), set_x(s.substr(i+1,s.size()-(i+1)),t);
// nao tem x em T
int tam,l1,l2;
tam = bst_y[0], l1 = i - bst_y[0] + 1, l2 = 0;
ans = max(ans, {tam,l1,l2});
for(int j=0; j<t.size()-1; j++){
tam = bst_x[j] + bst_y[j+1];
l1 = i - bst_y[j+1] + 1;
l2 = j - bst_x[j] + 1;
ans = max(ans, {tam,l1,l2});
}
// nao tem y em T
tam = bst_x[t.size()-1], l1 = i, l2 = t.size()-1 - bst_x[t.size()-1] + 1;
ans = max(ans, {tam, l1, l2});
}
reverse(s.begin(),s.end());
if(s == t){
cout << s.size() << '\n';
cout << 0 << ' ' << 0 << '\n';
return;
}
for(int i=0; i<s.size()-1; i++){
set_y(s.substr(0,i+1),t), set_x(s.substr(i+1,s.size()-(i+1)),t);
// nao tem x em T
int tam,l1,l2;
tam = bst_y[0], l1 = i, l2 = 0;
ans = max(ans, {tam,s.size()-1 - l1,l2});
for(int j=0; j<t.size()-1; j++){
tam = bst_x[j] + bst_y[j+1];
l1 = i + bst_x[j];
l2 = j - bst_x[j] + 1;
ans = max(ans, {tam,s.size()-1 - l1,l2});
}
// nao tem y em T
tam = bst_x[t.size()-1], l1 = i + bst_x[t.size()-1], l2 = t.size()-1 - bst_x[t.size()-1] + 1;
ans = max(ans, {tam,s.size()-1 - l1, l2});
}
cout << ans.tam << '\n' << ans.bs << ' ' << ans.bt << '\n';
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int ttt_ = 1;
// cin >> ttt_;
while(ttt_--) test();
return 0;
}
Compilation message (stderr)
necklace.cpp: In function 'void test()':
necklace.cpp:116:40: warning: narrowing conversion of '((s.std::__cxx11::basic_string<char>::size() - 1) - ((std::__cxx11::basic_string<char>::size_type)l1))' from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
116 | ans = max(ans, {tam,s.size()-1 - l1,l2});
| ~~~~~~~~~~~^~~~
necklace.cpp:121:44: warning: narrowing conversion of '((s.std::__cxx11::basic_string<char>::size() - 1) - ((std::__cxx11::basic_string<char>::size_type)l1))' from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
121 | ans = max(ans, {tam,s.size()-1 - l1,l2});
| ~~~~~~~~~~~^~~~
necklace.cpp:125:40: warning: narrowing conversion of '((s.std::__cxx11::basic_string<char>::size() - 1) - ((std::__cxx11::basic_string<char>::size_type)l1))' from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
125 | ans = max(ans, {tam,s.size()-1 - l1, l2});
| ~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |