Submission #503787

#	Time	Username	Problem	Language	Result	Execution time	Memory
503787		Victor	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	191 ms	464 KiB

necklace

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

vi kmp(string s,string p) {
    vi b(sz(p)+1);
    b[0]=-1;
    int i=0,j=-1;
    while(i<sz(p)) {
        while(0<=j&&p[i]!=p[j])j=b[j];
        ++j; ++i;
        b[i]=j;
    }
    
    vi ans(sz(s));
    i=0,j=0;
    while(i<sz(s)) {
        while(0<=j&&s[i]!=p[j])j=b[j];
        ++j;
        ans[i]=j;
        ++i;
        if(j==sz(p))j=b[j];
    }
    
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    string jill[2], jane[2];
    cin >> jill[0] >> jane[0];

    jill[1] = jill[0];
    reverse(all(jill[1]));

    jane[1] = jane[0];
    reverse(all(jane[1]));


    int n=sz(jill[0]),m=sz(jane[0]);
    int ans=0,sjill,sjane;
    rep(i,1,m) {
        vi lps=kmp(jill[0],jane[0].substr(i)),lsp=kmp(jill[1],jane[1].substr(m-i));
        rep(j,0,n-1) {
            int a=lps[j],b=lsp[n-j-2];
            if(a+b>ans) {
                ans=a+b;
                sjill=j-a+1;
                sjane=i-b;
            }
        }



        lps=kmp(jill[0],jane[1].substr(i)),lsp=kmp(jill[1],jane[0].substr(m-i));
        rep(j,0,n-1) {
            int a=lps[j],b=lsp[n-j-2];
            if(a+b>ans) {
                ans=a+b;
                sjill=j-a+1;
                sjane=m-i-a;
            }
        }
    }

    cout<<ans<<endl<<sjill<<' '<<sjane<<endl;
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'vi kmp(std::string, std::string)':
necklace.cpp:37:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while(i<sz(p)) {
      |            ^
necklace.cpp:45:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(i<sz(s)) {
      |            ^
necklace.cpp:50:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if(j==sz(p))j=b[j];
      |             ^
necklace.cpp: In function 'int main()':
necklace.cpp:96:34: warning: 'sjane' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     cout<<ans<<endl<<sjill<<' '<<sjane<<endl;
      |                                  ^~~~~
necklace.cpp:96:29: warning: 'sjill' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     cout<<ans<<endl<<sjill<<' '<<sjane<<endl;
      |                             ^~~

• Subtask 1: 15 / 15