Submission #546330

#	Time	Username	Problem	Language	Result	Execution time	Memory
546330		s_jaskaran_s	Necklace (Subtask 4) (BOI19_necklace4)	C++17	3 / 15	307 ms	444 KiB

necklace

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
#define endl '\n'
void zedd(string &s,string &t,int z[]){
    t+='#';
    z[0]=0;
    int x=0,y=0;
    for(int i=1;i<t.size();i++){
        z[i]=max(0,min(z[i-x],y-i+1));
        while(i+z[i]<t.size()&&t[z[i]]==t[z[i]+i]){
            z[i]++;
            x=i;
            y=i+z[i]-1;
        }
    }
    for(int i=0;i<s.size();i++){
        z[i+t.size()]=max(0,min(z[i+t.size()-x],y-(i+(int)t.size())+1));
        while(i+z[i+t.size()]<s.size()&&t[z[i+t.size()]]==s[z[i+t.size()]+i]){
            z[i+t.size()]++;
            x=i+t.size();
            y=i+t.size()+z[i+t.size()]-1;
        }
    }
    for(int i=0;i<s.size();i++){
        z[i]=z[i+t.size()];
    }
    t.pop_back();
}
void kmp(string &s,string &t,int x[]){
    if(t.size()==0){
        for(int i=0;i<s.size();i++){
            x[i]=0;
        }
        return;
    }
    int j=0;
    s=t+'#'+s;
    x[0]=0;
    for(int i=1;i<s.size();i++){
        while(j>0&&s[i]!=s[j]){
            j=x[j-1];
        }
        if(s[i]==s[j]){
            j++;
        }
        x[i]=j;
    }
    j=0;
    for(int i=0;i<s.size()-t.size()-1;i++){
        x[i]=x[i+t.size()+1];
    }
    s=s.substr(t.size()+1,s.size()-t.size()-1);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s,p,t;
    cin>>s>>p;
    for(int j=p.size()-1;j>=0;j--){
        t+=p[j];
    }
    int z[s.size()+p.size()+1];
    int y[s.size()+p.size()+1],x[s.size()+p.size()+1];
    int ans=0;
    int e,f;
    for(int i=0;i<s.size();i++){
        string r=s.substr(i,s.size()-i);
        zedd(p,r,z);
        r.clear();
        for(int j=i-1;j>=0;j--){
            r+=s[j];
        }
        kmp(t,r,y);
        for(int j=0;j<p.size();j++){
            x[j]=y[p.size()-j-1];
        }
        x[p.size()]=0;
        for(int j=0;j<p.size();j++){
            if(z[j]+x[j+z[j]]>ans){
                ans=z[j]+x[j+z[j]];
                e=i-x[j+z[j]];
                f=j;
            }
        }
    }
    p=t;
    t.clear();
    for(int j=p.size()-1;j>=0;j--){
        t+=p[j];
    }
    for(int i=0;i<s.size();i++){
        string r=s.substr(i,s.size()-1-i);
        zedd(p,r,z);
        r.clear();
        for(int j=i-1;j>=0;j--){
            r+=s[j];
        }
        kmp(t,r,y);
        for(int j=0;j<p.size();j++){
            x[j]=y[p.size()-j-1];
        }
        x[p.size()]=0;
        for(int j=0;j<p.size();j++){
            if(z[j]+x[j+z[j]]>ans){
                ans=z[j]+x[j+z[j]];
                e=i-x[j+z[j]];
                f=p.size()-1-j-ans+1;
            }
        }
    }
    cout<<ans<<endl;
    cout<<e<<" "<<f;
}

Compilation message (stderr)

necklace.cpp: In function 'void zedd(std::string&, std::string&, int*)':
necklace.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=1;i<t.size();i++){
      |                 ~^~~~~~~~~
necklace.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         while(i+z[i]<t.size()&&t[z[i]]==t[z[i]+i]){
      |               ~~~~~~^~~~~~~~~
necklace.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
necklace.cpp:24:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         while(i+z[i+t.size()]<s.size()&&t[z[i+t.size()]]==s[z[i+t.size()]+i]){
      |               ~~~~~~~~~~~~~~~^~~~~~~~~
necklace.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
necklace.cpp: In function 'void kmp(std::string&, std::string&, int*)':
necklace.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int i=0;i<s.size();i++){
      |                     ~^~~~~~~~~
necklace.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=1;i<s.size();i++){
      |                 ~^~~~~~~~~
necklace.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=0;i<s.size()-t.size()-1;i++){
      |                 ~^~~~~~~~~~~~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
necklace.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j=0;j<p.size();j++){
      |                     ~^~~~~~~~~
necklace.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int j=0;j<p.size();j++){
      |                     ~^~~~~~~~~
necklace.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
necklace.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int j=0;j<p.size();j++){
      |                     ~^~~~~~~~~
necklace.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(int j=0;j<p.size();j++){
      |                     ~^~~~~~~~~
necklace.cpp:118:14: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |     cout<<e<<" "<<f;
      |              ^~~
necklace.cpp:118:19: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |     cout<<e<<" "<<f;
      |                   ^

• Subtask 1: 3 / 15