제출 #1076506

#제출 시각아이디문제언어결과실행 시간메모리
1076506vjudge1Necklace (Subtask 4) (BOI19_necklace4)C++17
0 / 15
3 ms868 KiB
#include<bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; const int N = 3003; 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;//, cout << j << " "; } // cout << tmp << '\n'; } 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] + 1; kq.se = j - knuth[0][j] + 1; } } } reverse(t.begin(), t.end()); 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]; // cout << ans << " " << i << " " << j << " " << knuth[0][j] << " " << tmp << '\n'; kq.fi = i - knuth[1][rev - 1] + 1; kq.se = t.size() - (j + knuth[1][rev - 1]) + 1; } } } cout << ans << '\n'; cout << kq.fi << " " << kq.se; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

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:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
necklace.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int j = i; j < s.size(); j++)
      |                        ~~^~~~~~~~~~
necklace.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j = 1; j <= t.size(); j++)
      |                        ~~^~~~~~~~~~~
necklace.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
necklace.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int j = i; j < s.size(); j++)
      |                        ~~^~~~~~~~~~
necklace.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int j = 1; j <= t.size(); j++)
      |                        ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...