oj.uz

Submission #514515

# Submission time Handle Problem Language Result Execution time Memory
514515 2022-01-18T08:37:28 Z Mahdi Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
 494 ms 388 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=3e3+5;
int n, m, f[2*N], g[2*N];
string s, t, u;

void opr1(){
    int x;
    for(int i=1;i<u.size();++i){
        f[i]=0;
        x=f[i-1];
        while(true){
            if(u[i]==u[x]){
                f[i]=x+1;
                break;
            }
            if(x==0)
                break;
            x=f[x-1];
        }
    }
}

void opr2(){
    int x;
    for(int i=1;i<u.size();++i){
        g[i]=0;
        x=g[i-1];
        while(true){
            if(u[i]==u[x]){
                g[i]=x+1;
                break;
            }
            if(x==0)
                break;
            x=g[x-1];
        }
    }
}

pair<int, pii> kmp(bool bl){
    u=s+"#"+t;
    //cout<<u<<'\n';
    opr1();
    u=t+"#"+s;
    reverse(all(u));
    //cout<<u<<'\n';
    opr2();
    /*for(int i=0;i<u.size();++i)
        cout<<f[i]<<' ';
    cout<<'\n';
    for(int i=0;i<u.size();++i)
        cout<<g[i]<<' ';
    cout<<"\n\n";*/
    pair<int, pii> z;
    int x;
    for(int i=0;i<m-1;++i){
        x=f[1+n+i]+g[n+m-1-i];
        if((bl && x>=z.F) || x>z.F){
            z.F=x;
            z.S.F=g[n+m-1-i];
            z.S.S=i-f[1+n+i]+1;
        }
    }
    if((!bl && g[n+m]>=z.F) || g[n+m]>z.F){
        z.F=g[n+m];
        z.S.F=g[n+m];
        z.S.S=0;
    }
    if((bl && f[m+n]>=z.F) || f[m+n]>z.F){
        z.F=f[m+n];
        z.S.F=0;
        z.S.S=m-f[m+n];
    }
    return z;
}

pair<int, pii> sol(bool bl){
    pair<int, pii> res, c;
    res.F=0;
    for(int i=0;i<n;++i){
        //cout<<i<<" : \n";
        c=kmp(bl);
        if(c.F>res.F){
            c.S.F=i-c.S.F;
            res=c;
        }
        char z=s[0];
        for(int j=0;j<n-1;++j)
            s[j]=s[j+1];
        s[n-1]=z;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>s>>t;
    s+="*";
    n=s.size();
    m=t.size();
    pair<int, pii>ans, c;
    ans=sol(0);
    reverse(all(t));
    c=sol(1);
    if(c.F>ans.F){
        c.S.S=m-c.S.S-c.F;
        ans=c;
    }
    cout<<ans.F<<'\n';
    cout<<ans.S.F<<' '<<ans.S.S<<'\n';
}

Compilation message

necklace.cpp: In function 'void opr1()':
necklace.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=1;i<u.size();++i){
      |                 ~^~~~~~~~~
necklace.cpp: In function 'void opr2()':
necklace.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=1;i<u.size();++i){
      |                 ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 384 KB Output is correct
2 Correct 350 ms 384 KB Output is correct
3 Correct 494 ms 380 KB Output is correct
4 Correct 365 ms 308 KB Output is correct
5 Correct 192 ms 380 KB Output is correct
6 Correct 201 ms 332 KB Output is correct
7 Correct 290 ms 376 KB Output is correct
8 Correct 360 ms 388 KB Output is correct
9 Correct 361 ms 332 KB Output is correct