Submission #1076688

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1076688	2024-08-26T15:35:20 Z	Namviet2704	Necklace (Subtask 4) (BOI19_necklace4)	C++17	Compilation error	0 ms	0 KB

necklace

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;

const int N = 6003;

string s, t;
int pi[2][N], knuth[2][N];
int ans = 0;
pair<int, int> kq;

void kmp(string &s, string &t, int x)
{
    string tmp = s + '0' + t;
    int n = tmp.size();
    for (int i = 1; i < n; i++)
    {
        int j = pi[x][i - 1];
        while (j > 0 && tmp[i] != tmp[j])
            j = pi[x][j - 1];
        if (tmp[i] == tmp[j])
            j++;
        pi[x][i] = j;
        if(i > s.size())
            knuth[x][i - s.size()] = j;
    }
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> s >> t;
    for(int i = 0; i < s.size(); i++)
    {
        string tmp = "";
        for(int j = i; j < s.size(); j++)
            tmp = tmp + s[j];
        kmp(tmp, t, 0);
        tmp = "";
        reverse(t.begin(), t.end());
        for(int j = i - 1; j >= 0; j--)
            tmp = tmp + s[j];
        kmp(tmp, t, 1);
        reverse(t.begin(), t.end());
        for(int j = 1; j <= t.size(); j++)
        {
            int rev = t.size() - j + 1;
            if(ans < knuth[0][j] + knuth[1][rev - 1])
            {
                ans = knuth[0][j] + knuth[1][rev - 1];
                kq.fi = i - knuth[1][rev - 1];
                kq.se = j - knuth[0][j];
            }
        }
    }
    reverse(t.begin(), t.end());
    for(int i = 0; i < min(s.size(), 1000); i++)
    {
        string tmp = "";
        for(int j = i; j < s.size(); j++)
            tmp = tmp + s[j];
        kmp(tmp, t, 0);
        tmp = "";
        reverse(t.begin(), t.end());
        for(int j = i - 1; j >= 0; j--)
            tmp = tmp + s[j];
        kmp(tmp, t, 1);
        reverse(t.begin(), t.end());
        for(int j = 1; j <= t.size(); j++)
        {
            int rev = t.size() - j;
            cout << j << " " << rev << '\n';
            if(ans < knuth[0][j] + knuth[1][rev])
            {
                ans = knuth[0][j] + knuth[1][rev];
                kq.fi = i - knuth[1][rev];
                kq.se = t.size() - (j + knuth[1][rev]);
            }
        }
    }
    cout << ans << '\n';
    cout << kq.fi << " " << kq.se;
    return 0;
}

Compilation message

necklace.cpp: In function 'void kmp(std::string&, std::string&, int)':
necklace.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if(i > s.size())
      |            ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
necklace.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = i; j < s.size(); j++)
      |                        ~~^~~~~~~~~~
necklace.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j = 1; j <= t.size(); j++)
      |                        ~~^~~~~~~~~~~
necklace.cpp:61:42: error: no matching function for call to 'min(std::__cxx11::basic_string<char>::size_type, int)'
   61 |     for(int i = 0; i < min(s.size(), 1000); i++)
      |                                          ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from necklace.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
necklace.cpp:61:42: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
   61 |     for(int i = 0; i < min(s.size(), 1000); i++)
      |                                          ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from necklace.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
necklace.cpp:61:42: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
   61 |     for(int i = 0; i < min(s.size(), 1000); i++)
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from necklace.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
necklace.cpp:61:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
   61 |     for(int i = 0; i < min(s.size(), 1000); i++)
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from necklace.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
necklace.cpp:61:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
   61 |     for(int i = 0; i < min(s.size(), 1000); i++)
      |                                          ^
necklace.cpp:64:26: 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 = i; j < s.size(); j++)
      |                        ~~^~~~~~~~~~
necklace.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j = 1; j <= t.size(); j++)
      |                        ~~^~~~~~~~~~~