Submission #530083

#	Time	Username	Problem	Language	Result	Execution time	Memory
530083		vivo2006	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	300 ms	812 KiB

necklace

//BOI 2019 - Necklace
#include<bits/stdc++.h>
using namespace std;
int p1[6002], p2[6002];
string s1, s2;
pair<pair<int, int>, int> ans;
void KMP(string s, int* p)
{
    int i, len;
    for(i = 1; i < s.size(); i ++)
    {
        len = p[i - 1];
        while(len && s[i] != s[len]) len = p[len - 1];
        if(s[i] == s[len]) p[i] = len + 1;
        else p[i] = 0;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    int i, j, lft, rgt;
    cin>>s1>>s2;
    string leftS2 = s2, rightS2 = s2;
    reverse(leftS2.begin(), leftS2.end());
    for(i = 0; i < s1.size(); i ++)
    {
        string leftS1 = s1.substr(0, i), rightS1 = s1.substr(i);
        reverse(leftS1.begin(), leftS1.end());
        KMP(leftS1 + "#" + rightS2, p1);
        KMP(rightS1 + "#" + leftS2, p2);
        for(j = 1; j <= s2.size(); j ++)
        {
            ans = max(ans, {{p1[i + j] + p2[s1.size() + s2.size() - i - j], i - p1[i + j]}, j - p1[i + j]});
            //cout<<i<<" "<<j<<" : "<<p1[i + j]<<" "<<p2[s1.size() + s2.size() - i - j]<<endl;
            //cout<<i<<" "<<j<<" : "<<j - p1[i + j]<<'\n';
        }

    }
    //cout<<s2.size()<<endl;
    reverse(s2.begin(), s2.end());
    leftS2 = s2, rightS2 = s2;
    reverse(leftS2.begin(), leftS2.end());
    for(i = 0; i < s1.size(); i ++)
    {
        string leftS1 = s1.substr(0, i), rightS1 = s1.substr(i);
        reverse(leftS1.begin(), leftS1.end());
        //cout<<leftS1<<"#"<<rightS2<<" "<<rightS1<<"#"<<leftS2<<endl;
        KMP(leftS1 + "#" + rightS2, p1);
        KMP(rightS1 + "#" + leftS2, p2);
        for(j = 1; j <= s2.size(); j ++)
        {
            ans = max(ans, {{p1[i + j] + p2[s1.size() + s2.size() - i - j], i - p1[i + j]}, s2.size() - j - p2[s1.size() + s2.size() - i - j]});
            //cout<<i<<" "<<j<<" : "<<s2.size() - j - p2[s1.size() + s2.size() - i - j]<<'\n';
        }
    }
    cout<<ans.first.first<<"\n"<<ans.first.second<<" "<<ans.second<<endl;
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void KMP(std::string, int*)':
necklace.cpp:10:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(i = 1; i < s.size(); i ++)
      |                ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(i = 0; i < s1.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(j = 1; j <= s2.size(); j ++)
      |                    ~~^~~~~~~~~~~~
necklace.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(i = 0; i < s1.size(); i ++)
      |                ~~^~~~~~~~~~~
necklace.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(j = 1; j <= s2.size(); j ++)
      |                    ~~^~~~~~~~~~~~
necklace.cpp:22:15: warning: unused variable 'lft' [-Wunused-variable]
   22 |     int i, j, lft, rgt;
      |               ^~~
necklace.cpp:22:20: warning: unused variable 'rgt' [-Wunused-variable]
   22 |     int i, j, lft, rgt;
      |                    ^~~

• Subtask 1: 15 / 15