Submission #1113643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113643		vjudge1	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	116 ms	35664 KiB

necklace

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void init()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
}

vector<int> PrefixFunction(string &pattern)
{
    int m = pattern.size();
    vector<int> table(m);

    for (int i = 1, k = 0; i < m; i++)
    {
        while (k > 0 && pattern[i] != pattern[k])
            k = table[k - 1];

        if (pattern[k] == pattern[i])
            table[i] = ++k;
        else
            table[i] = k;
    }

    return table;
}

const int max_n = 3003;

int c[max_n][max_n], ans, l, r;
string s1, s2;

void solve(bool t){
    for (int i = 0; i < max_n; i++) {
        for (int j = 0; j < max_n; j++)
            c[i][j] = 0;
    }

    for (int i = 0; i < s1.size(); i++) {
        string s = s1.substr(i) + "#" + s2;
        vector<int> p = PrefixFunction(s);
        for (int j = s2.size() - 1; j > -1; j--) {
            c[i][j] = p.back();
            p.pop_back();
        }
    }

    for (int i = 0; i < s1.size(); i++){
        for (int j = 0; j < s2.size(); j++) {
            int val = c[i][j];
           if(j - val > 0)
               val += c[i + val][j - val];
            if(val > ans){
                ans = val;
                r = j - val + 1;
                if(t)
                    l = i;
                else
                    l = s1.size() - i - val;
            }
        }
    }
}
int main()
{
    init();
    // freopen("differences.in", "r", stdin);
    // freopen("mootube.out", "w", stdout);
    ans = 0, l = 0, r = 0;
    cin >> s1 >> s2;

    solve(1);
    reverse(s1.begin(), s1.end());
    solve(0);
    cout << ans << "\n"
         << l << " " << r;
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void solve(bool)':
necklace.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < s1.size(); i++) {
      |                     ~~^~~~~~~~~~~
necklace.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < s1.size(); i++){
      |                     ~~^~~~~~~~~~~
necklace.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j = 0; j < s2.size(); j++) {
      |                         ~~^~~~~~~~~~~

• Subtask 1: 0 / 15