Submission #348013

#	Time	Username	Problem	Language	Result	Execution time	Memory
348013		elizarv	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	247 ms	620 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T a,Args... args) {cout<<a<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define SZ(x) int(x.size())
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

vector<int> prefix_function(string &s) {
    int n = s.size();
    vector<int> pf(n);
    pf[0] = 0;
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) j = pf[j-1];
        if (s[i] == s[j]) j++;
        pf[i] = j;
    }
    return pf;
}

vector<int> kmp(string &s, string &p) {
    int n = s.size(), m = p.size(), cnt = 0;
    vector<int> mx(n, 0);
    if(!m)return mx;
    vector<int> pf = prefix_function(p);
    for(int i = 0, j = 0; i < n; i++) {
        while(j && s[i] != p[j]) j = pf[j-1];
        if(s[i] == p[j]) j++;
        mx[i] = j;
        if(j == m) {
            cnt++;
            j = pf[j-1];
        }
    }
    return mx;
}

int ans, a, b;

void go(string &s, string &t, bool f = false){
    int n = s.size();
    int m = t.size();
    string rev = t;
    reverse(rev.begin(), rev.end());
    forn(i, 0, n){
        string lf = s.substr(0, i);
        string rg = s.substr(i, n-i);
        reverse(lf.begin(), lf.end());
        vector<int> suf = kmp(rev, lf);
        vector<int> pref = kmp(t, rg);
        reverse(suf.begin(), suf.end());
        forn(j, 0, m){
            if(pref[j] + j < m){
                int aux = pref[j] + suf[j+1];
                if(ans < aux){
                    ans = aux;
                    if(f){
                        a = m - i - pref[j];
                        b = j - pref[j] - 1;;
                    }else{
                        a = i - suf[j+1];
                        b = j - pref[j] + 1;
                    }
                }
            }
        }
    }
}


int main() {
 ios::sync_with_stdio(0); cin.tie(0);

   string s, t;
   cin >> s >> t;

   go(s, t);
   reverse(t.begin(), t.end());
   go(s, t, true);
   cout << ans << endl;
   cout << a << " " << b << endl;



 }

• Subtask 1: 0 / 15