Submission #684071

#	Time	Username	Problem	Language	Result	Execution time	Memory
684071		danikoynov	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	221 ms	436 KiB

necklace

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 20010;

string s, t;
int pf[maxn], pb[maxn], n, m;
int nxt[maxn], bef[maxn];
void solve_front(string s)
{
    reverse(s.begin(), s.end());
    for (int i = 1; i < s.size(); i ++)
    {
        int j = pf[i - 1];
        while(j > 0 && s[j] != s[i])
            j = pf[j - 1];
        if (s[j] == s[i])
            j ++;
        pf[i] = j;
    }

    int to = 0;
    for (int j = t.size() - 1; j >= 0; j --)
    {
        while(to > 0 && s[to] != t[j])
            to = pf[to - 1];
        if (s[to] == t[j])
            to ++;
        nxt[j] = to;
    }
}

void solve_back(string s)
{
    for (int i = 1; i < s.size(); i ++)
    {
        int j = pb[i - 1];
        while(j > 0 && s[j] != s[i])
            j = pb[j - 1];
        if (s[j] == s[i])
            j ++;
        pb[i] = j;
    }

    int to = 0;
    for (int j = 0; j < t.size(); j ++)
    {
        while(to > 0 && s[to] != t[j])
            to = pb[to - 1];
        if (s[to] == t[j])
            to ++;
        bef[j] = to;
    }
}

void solve()
{
    cin >> s >> t;
    n = s.size();
    m = t.size();

    int ans = 0, p1 = -1, p2 = -1;
    for (int i = 0; i < n; i ++)
    {
        string ft = s.substr(0, i);
        solve_front(ft);
        string bk = s.substr(i, n);
        solve_back(bk);

        for (int j = 0; j < m; j ++)
        {
            int sum = nxt[j];
            if (j != 0)
                sum = sum + bef[j - 1];
            if (sum > ans)
            {
                ans = sum;
                ///cout << i << " : " << j << " " << bef[j - 1] << " " << nxt[j] << endl;
                p1 = i - nxt[j] + 1;
                p2 = j + 1;
                if (j != 0)
                    p2 = p2 - bef[j - 1];
            }
        }
    }

    reverse(t.begin(), t.end());
        for (int i = 0; i < n; i ++)
    {
        string ft = s.substr(0, i);
        solve_front(ft);
        string bk = s.substr(i, n);
        solve_back(bk);

        for (int j = 0; j < m; j ++)
        {
            int sum = nxt[j];
            if (j != 0)
                sum = sum + bef[j - 1];
            if (sum > ans)
            {
                ans = sum;
                ///cout << i << " : " << j << " " << bef[j - 1] << " " << nxt[j] << endl;
                p1 = i - nxt[j] + 1;
                p2 = j + 1;
                if (j != 0)
                    p2 = p2 - bef[j - 1];

                p2 = m - p2 + 1;
                p2 = p2 - sum + 1;
            }
        }
    }
    reverse(t.begin(), t.end());
    //string s1 = s.substr(p1 - 1, ans);
    //string s2 = t.substr(p2 - 1, ans);
    ///cout << s1 << " " << s2 << endl;
    if (ans == 0)
    {
        cout << 0 << " " << endl << 0 << " " << 0 << endl;
        return;
    }
    cout << ans << " " << endl << p1 - 1 << " " << p2 - 1 << endl;


}

int main()
{
    ///freopen("test.in", "r", stdin);
    solve();
    return 0;
}
/**

yxbadctz
*/

Compilation message (stderr)

necklace.cpp: In function 'void solve_front(std::string)':
necklace.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 1; i < s.size(); i ++)
      |                     ~~^~~~~~~~~~
necklace.cpp: In function 'void solve_back(std::string)':
necklace.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 1; i < s.size(); i ++)
      |                     ~~^~~~~~~~~~
necklace.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int j = 0; j < t.size(); j ++)
      |                     ~~^~~~~~~~~~

• Subtask 1: 15 / 15