답안 #854068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854068	2023-09-26T04:52:46 Z	GoldLight	Necklace (Subtask 4) (BOI19_necklace4)	C++17	3 / 15	1079 ms	600 KB

necklace

#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}

vector<int> f1(string &s, string &t){
    int n=s.size(), m=t.size(), j=0;
    vector<int> a(n), b(m);
    for(int i=1; i<n; i++){
        while(j>0 && s[i]!=s[j]) j=a[j-1];
        if(s[i]==s[j]) j++;
        a[i]=j;
    }
    j=0;
    for(int i=0; i<m; i++){
        while(j==n || (j>0 && s[j]!=t[i])) j=a[j-1];
        if(s[j]==t[i]) j++;
        b[i]=j;
    }
    return b;
}
vector<int> f2(string &s, string &t){
    int n=s.size(), m=t.size(), j=0;
    vector<int> a(n), b(m);
    for(int i=1; i<n; i++){
        while(j>0 && s[i]!=s[j]) j=a[j-1];
        if(s[i]==s[j]) j++;
        a[i]=j;
    }
    j=0;
    for(int i=m-1; i>=0; i--){
        while(j==n || (j>0 && s[j]!=t[i])) j=a[j-1];
        if(s[j]==t[i]) j++;
        b[i]=j;
    }
    return b;
}
int main(){
    fast();
    string s, t1, t2; cin>>s>>t1;
    t2=t1; reverse(t2.begin(), t2.end());
    int n=s.size(), m=t1.size();
    int ki=1, ka=n, ans, j1, j2;
    while(ki<=ka){
        int k=(ki+ka)/2;
        bool cek=false;
        for(int l=0; l+k-1<n; l++){
            if(cek) break;
            if(k>m){
                cek=true;
                break;
            }
            string s1=s.substr(l, k);
            string s2=s1; reverse(s2.begin(), s2.end());
            auto val1=f1(s1, t1), val2=f2(s2, t1), val3=f1(s1, t2), val4=f2(s2, t2);
            for(int i=0; i+k-1<m; i++){
                if(val1[i+k-1]+val2[i]>=k){
                    ans=k, j1=l, j2=i;
                    cek=true;
                    break;
                }
            }
            for(int i=0; i+k-1<m; i++){
                if(val3[i+k-1]+val4[i]>=k){
                    ans=k, j1=l, j2=m-(i+k-1)-1;
                    cek=true;
                    break;
                }
            }
            // if(ans==k){
            //     cout<<s1<<'\n';
            //     for(int i=0; i<m; i++) cout<<val3[i]<<' ';
            //     cout<<'\n';
            //     for(int i=0; i<m; i++) cout<<val4[i]<<' ';
            //     cout<<'\n';
            // }
        }
        if(cek) ki=k+1;
        else ka=k-1;
    }
    cout<<ans<<'\n';
    cout<<j1<<' '<<j2;
}
//KMP
/*
vector<int> f(string &s){
    int n=s.size(), j=0;
    vector<int> v(n);
    for(int i=1; i<n; i++){
        while(j>0 && s[i]!=s[j]) j=v[j-1];
        if(s[i]==s[j]) j++;
        v[i]=j;
    }
    return v;
}
int main(){
    fast();
    string s, t; cin>>s>>t;
    string temp=t+'0'+s;
    auto lps=f(temp);
    int ans=0;
    for(auto i:lps) ans+=(i==t.size());
    cout<<ans;
}*/

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:81:20: warning: 'j2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     cout<<j1<<' '<<j2;
      |                    ^~
necklace.cpp:81:15: warning: 'j1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     cout<<j1<<' '<<j2;
      |               ^~~
necklace.cpp:80:16: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |     cout<<ans<<'\n';
      |                ^~~~

Subtask #1

3.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	344 KB	Output is correct
2	Partially correct	127 ms	508 KB	Output is partially correct
3	Correct	1079 ms	508 KB	Output is correct
4	Correct	664 ms	496 KB	Output is correct
5	Partially correct	416 ms	344 KB	Output is partially correct
6	Partially correct	592 ms	344 KB	Output is partially correct
7	Correct	612 ms	500 KB	Output is correct
8	Correct	895 ms	600 KB	Output is correct
9	Partially correct	651 ms	344 KB	Output is partially correct