Submission #976355

#	Time	Username	Problem	Language	Result	Execution time	Memory
976355		roctes7	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	37 / 85	244 ms	82712 KiB

necklace

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
const double eps = 1e-6;
const int MAX = 3e3+3;

int pi[3003][7003];
int n;
string s;


void kmp(int sta){
    for (int i = 1; i < n; i++){
        int j = pi[sta][i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[sta][j-1];
        if (s[i] == s[j])
            j++;
        pi[sta][i] = j;
    }
}

string t1,t2;
pair<int,pair<int,int>> solve(){
       for(int i=0;i<t1.size();i++){
        s = "";
        for(int j=i;j<t1.size();j++)s+=t1[j];
        for(int j=0;j<i;j++)s+="$";
        s+="#";
        s+=t2;
        n = s.size();
        kmp(i);
        //cout<<s<<endl;
   }



   int ans = -1;
   int ansl = -1;
   int ansr = -1;

           for(int i=0;i<t1.size();i++){
            for(int j=t1.size()+1;j<n;j++){
                int cur = pi[i][j];
                    if(cur>ans){
                        ans = cur;
                        ansl = i;
                        ansr = j-(t1.size()+1)-ans+1;
                    }

                if(i+cur>=t1.size()||j-cur<t1.size()+1)continue;

                int cur2 = pi[i+cur][j-cur];
                    if(cur+cur2>ans){
                        ans = cur+cur2;
                        ansl = i;
                        ansr = j-(t1.size()+1)-ans+1;
                    }

            }
        }

   return {ans,{ansl,ansr}};
}


int main(){
    fastio;



   cin>>t1>>t2;



     auto ans1 = solve();


    reverse(t2.begin(),t2.end());

    auto ans2 = solve();
    ans2.se.se = ans2.se.se + ans2.fi-1;
    ans2.se.se = t2.size()-ans2.se.se-1;

    assert(ans2.se.se>=0);
    //if(ans2.se.se<0)ans2.se.se = t2.size()+ans2.se.se;



    pair<int,pair<int,int>> ans = max({ans1,ans2});



    cout<<ans.fi<<endl<<ans.se.fi<<" "<<ans.se.se;

    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'std::pair<int, std::pair<int, int> > solve()':
necklace.cpp:30:21: 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<t1.size();i++){
      |                    ~^~~~~~~~~~
necklace.cpp:32:22: 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 j=i;j<t1.size();j++)s+=t1[j];
      |                     ~^~~~~~~~~~
necklace.cpp:47:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |            for(int i=0;i<t1.size();i++){
      |                        ~^~~~~~~~~~
necklace.cpp:56:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                 if(i+cur>=t1.size()||j-cur<t1.size()+1)continue;
      |                    ~~~~~^~~~~~~~~~~
necklace.cpp:56:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                 if(i+cur>=t1.size()||j-cur<t1.size()+1)continue;
      |                                      ~~~~~^~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 4 / 20
• Subtask 3: 8 / 40