Submission #1208831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208831		sabino1	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	217 ms	576 KiB

necklace

#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});
      |                             ~~~~~~~~~~~^~~~

• Subtask 1: 15 / 15