Submission #773115

#	Time	Username	Problem	Language	Result	Execution time	Memory
773115		hungby04	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	177 ms	604 KiB

necklace

/// HuDzG
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll long long
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 9000000000000000000
#define F first
#define S second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pb push_back
#define mp make_pair
#define nmax 1000005
#define HUNGIT ""
#define MOD 1000000007

using namespace std;

string s, t;
int res = 0;
pii pos;

vector <int> kmp(string t, string s, bool ok)
{
    t += ' ';
    vector <int> pi(t.length(), 0), res(s.length(), 0);
    for(int i = 1, j = 0; i < t.length(); i++)
    {
        while(j > 0 && t[i] != t[j]) j = pi[j - 1];
        if(t[i] == t[j]) j++;
        pi[i] = j;
    }
    for(int i = 0, j = 0; i < s.length(); i++)
    {
        while(j > 0 && s[i] != t[j]) j = pi[j - 1];
        if(s[i] == t[j]) j++;
        res[i] = j;
    }
    if(!ok) reverse(res.begin(), res.end());
    res.pb(0);
    return res;
}

void calc(string s, string t, bool ok)
{
    // cout << t << endl;
    string tmp = t;
    reverse(tmp.begin(), tmp.end());
    for(int i = 0; i <= s.length(); i++)
    {
        string x = s.substr(0, i), y = s.substr(i, (int)s.length() - i);
        reverse(x.begin(), x.end());
        vector <int> l = kmp(y, t, 1), r = kmp(x, tmp, 0);
        // cout << i << " " << r[0] << endl;
        if(r[0] > res)
        {
            res = r[0];
            pos = mp(i - r[0], ok ? 0 : (t.length() - 1) - r[0]);
            // cout << i << " " << r[0] << endl;
        }
        for(int j = 0; j < t.length(); j++)
            if(l[j] + r[j + 1] > res)
            {
                res = l[j] + r[j + 1];
                pos = mp(i - r[j + 1], ok ? j - l[j] + 1 : (t.length() - 1) - (j + r[j + 1]));
                // cout << y << " " << res << " " << i << " " << j << " " << l[j] << endl;
            }
    }
}

void solve()
{
    cin >> s >> t;
    calc(s, t, 1);
    reverse(t.begin(), t.end());
    calc(s, t, 0);
    cout << res << " " << pos.F << " " << pos.S;
}

AutoAC
{
    // clock_t START, FINISH;
    // START = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen (HUNGIT".inp", "r", stdin);
    // freopen (HUNGIT".out", "w", stdout);
    int T = 1;

    // cin >> T;

    for (int i = 1; i <= T; i++)
    {
        solve();
    }

    // FINISH = clock();
    // cout << fixed << setprecision(4);
    // cout << endl << "TIME: " << (ld)((ld)(FINISH - START) / CLOCKS_PER_SEC);
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'std::vector<int> kmp(std::string, std::string, bool)':
necklace.cpp:29:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 1, j = 0; i < t.length(); i++)
      |                           ~~^~~~~~~~~~~~
necklace.cpp:35:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0, j = 0; i < s.length(); i++)
      |                           ~~^~~~~~~~~~~~
necklace.cpp: In function 'void calc(std::string, std::string, bool)':
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(int i = 0; i <= s.length(); i++)
      |                    ~~^~~~~~~~~~~~~
necklace.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0; j < t.length(); j++)
      |                        ~~^~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40