Submission #146457

#	Time	Username	Problem	Language	Result	Execution time	Memory
146457		Alexa2001	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	269 ms	612 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 3005;


string A, B, Brev;
int startA, startB, best = 0;

int z1[Nmax], z2[Nmax];
int pi[Nmax];

void kmp(string &A, string &B, int mat[])
{
    int i, k;

    pi[1] = 0;
    for(i=2; i<=A.size(); ++i)
    {
        k = pi[i-1];
        while(k && A[k] != A[i-1]) k = pi[k];
        
        if(A[k] == A[i-1]) ++k;
        pi[i] = k;
    }

    k = 0;
    for(i=1; i<=B.size(); ++i)
    {
        while(k && A[k] != B[i-1]) k = pi[k];

        if(A[k] == B[i-1]) ++k;
        mat[i-1] = k;
    }
}

void solve(bool rev)
{
    if(rev) swap(B, Brev);

    int i, j;

    for(i=0; i<=A.size(); ++i)
    {
        string A1, A2;

        A1 = A.substr(0, i); /// 0...i-1
        A2 = A.substr(i, A.size() - i); /// i...A.size()-1

     //   cerr << i << ' ' << A1 << ' ' << A2 << ' ' << '\n';

        reverse(A1.begin(), A1.end());
            
        kmp(A1, Brev, z1);
        kmp(A2, B, z2);

        for(j=0; j<=B.size(); ++j)
        {
            int curr;
            int curr1 = 0, curr2 = 0;
            if(j > 0) curr1 = z2[j-1];
            if(j < B.size()) curr2 = z1[B.size() - j - 1];
            
            curr = curr1 + curr2;

            if(curr > best) 
            {
   /*            if(curr == 4)
                {
                    cerr << (rev ? 1 : 0) << '\n';
                    cerr << A1 << ' ' << A2 << '\n';
                    cerr << curr1 << ' ' << curr2 << '\n';
                }
*/
                best = curr;
                startA = i - curr2;
                startB = j - curr1;

                if(rev) startB = B.size() - 1 - startB - curr + 1;
            }
        }
    }
}

int main()
{
  //  freopen("necklace.in", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> A >> B;

    Brev = B;
    reverse(Brev.begin(), Brev.end());
    
    solve(0);
    solve(1);

    cout << best << '\n' << startA << ' ' << startB << '\n';

    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void kmp(std::__cxx11::string&, std::__cxx11::string&, int*)':
necklace.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=2; i<=A.size(); ++i)
              ~^~~~~~~~~~
necklace.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1; i<=B.size(); ++i)
              ~^~~~~~~~~~
necklace.cpp: In function 'void solve(bool)':
necklace.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<=A.size(); ++i)
              ~^~~~~~~~~~
necklace.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<=B.size(); ++j)
                  ~^~~~~~~~~~
necklace.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j < B.size()) curr2 = z1[B.size() - j - 1];
                ~~^~~~~~~~~~

• Subtask 1: 15 / 15