Submission #513763

#	Time	Username	Problem	Language	Result	Execution time	Memory
513763		Mahdi	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	17 / 85	354 ms	392 KiB

necklace

#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==f[x])
                break;
            x=f[x];
        }
    }
}

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==g[x])
                break;
            x=g[x];
        }
    }
}

pair<int, pii> kmp(){
    u=s+"#"+t;
    opr1();
    u=t+"#"+s;
    reverse(all(u));
    opr2();
    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(x>z.F){
            z.F=x;
            z.S.F=g[n+m-1-i];
            z.S.S=i-f[1+n+i]+1;
        }
    }
    if(g[n+m]>z.F){
        z.F=g[n+m];
        z.S.F=g[n+m];
        z.S.S=0;
    }
    if(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(){
    pair<int, pii> res, c;
    res.F=0;
    for(int i=0;i<n;++i){
        c=kmp();
        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();
    reverse(all(t));
    c=sol();
    if(c.F>ans.F){
        c.S.S=m-c.S.S-c.F;
        ans=c;
    }
    cout<<ans.F<<'\n'<<ans.S.F<<' '<<ans.S.S<<'\n';
}
/*
xnvnnqfwnxcvzyakzhnpepdbadkjktyqktjasudbxaasmkfnphalwubd
zjnvfbfqalosvcdabdpepnhzjtkqytkjkcczu

vzyakzhnpepdbadkjktyqktjasudbxaasmkfnphalwubd
alosvcdabdpepnhzjtkqytkjkcczu

vzyakzhnpepdbadkjktyqktjasudb
alosvcdabdpepnhzjtkqytkjkcczu

zhnpepdbadkjktyqktj
dabdpepnhzjtkqytkjk
*/

Compilation message (stderr)

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: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 8 / 40