oj.uz

Submission #146457

# Submission time Handle Problem Language Result Execution time Memory
146457 2019-08-24T07:50:41 Z Alexa2001 Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
 269 ms 612 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 384 KB Output is correct
2 Correct 192 ms 508 KB Output is correct
3 Correct 269 ms 476 KB Output is correct
4 Correct 188 ms 480 KB Output is correct
5 Correct 140 ms 612 KB Output is correct
6 Correct 157 ms 436 KB Output is correct
7 Correct 176 ms 432 KB Output is correct
8 Correct 200 ms 432 KB Output is correct
9 Correct 206 ms 432 KB Output is correct