Submission #773099

# Submission time Handle Problem Language Result Execution time Memory
773099 2023-07-04T15:10:29 Z hungby04 Necklace (Subtask 4) (BOI19_necklace4) C++17
0 / 15
175 ms 472 KB
/// 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);
        if(r[0] > res)
        {
            res = r[0];
            pos = mp(i - r[0], ok ? 0 : (t.length() - 1) - r[0]);
        }
        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]));
                // 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

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:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int j = 0; j < t.length(); j++)
      |                        ~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 175 ms 468 KB Output is correct
2 Incorrect 141 ms 472 KB Output isn't correct
3 Halted 0 ms 0 KB -