Submission #530037

#TimeUsernameProblemLanguageResultExecution timeMemory
530037vivo2006Necklace (Subtask 4) (BOI19_necklace4)C++14
0 / 15
311 ms432 KiB
//BOI 2019 - Necklace #include<bits/stdc++.h> using namespace std; int p1[6002], p2[6002]; string s1, s2; pair<pair<int, int>, int> ans; void KMP(string s, int* p) { int i, len; for(i = 1; i < s.size(); i ++) { len = p[i - 1]; while(len && s[i] != s[len]) len = p[len - 1]; if(s[i] == s[len]) p[i] = len + 1; else p[i] = 0; } } int main() { int i, j, lft, rgt; cin>>s1>>s2; string leftS2 = s2, rightS2 = s2; reverse(leftS2.begin(), leftS2.end()); for(i = 0; i < s1.size(); i ++) { string leftS1 = s1.substr(0, i), rightS1 = s1.substr(i); reverse(leftS1.begin(), leftS1.end()); KMP(leftS1 + "#" + rightS2, p1); KMP(rightS1 + "#" + leftS2, p2); for(j = 1; j <= s2.size(); j ++) { ans = max(ans, {{p1[i + j] + p2[s1.size() + s2.size() - i - j], i - p1[i + j]}, j - p1[i + j]}); //cout<<i<<" "<<j<<" : "<<p1[i + j]<<" "<<p2[s1.size() + s2.size() - i - j]<<endl; } } reverse(rightS2.begin(), rightS2.end()); reverse(leftS2.begin(), leftS2.end()); for(i = 0; i < s1.size(); i ++) { string leftS1 = s1.substr(0, i), rightS1 = s1.substr(i); reverse(leftS1.begin(), leftS1.end()); KMP(leftS1 + "#" + rightS2, p1); KMP(rightS1 + "#" + leftS2, p1); for(j = 1; j <= s2.size(); j ++) { ans = max(ans, {{p1[i + j] + p2[s1.size() + s2.size() - i - j], i - p1[i + j]}, s2.size() - j - p2[s1.size() + s2.size() - i - j]}); } } cout<<ans.first.first<<"\n"<<ans.first.second<<" "<<ans.second<<endl; return 0; }

Compilation message (stderr)

necklace.cpp: In function 'void KMP(std::string, int*)':
necklace.cpp:10:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(i = 1; i < s.size(); i ++)
      |                ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(i = 0; i < s1.size(); i ++)
      |                ~~^~~~~~~~~~~
necklace.cpp:30:22: 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(j = 1; j <= s2.size(); j ++)
      |                    ~~^~~~~~~~~~~~
necklace.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(i = 0; i < s1.size(); i ++)
      |                ~~^~~~~~~~~~~
necklace.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(j = 1; j <= s2.size(); j ++)
      |                    ~~^~~~~~~~~~~~
necklace.cpp:20:15: warning: unused variable 'lft' [-Wunused-variable]
   20 |     int i, j, lft, rgt;
      |               ^~~
necklace.cpp:20:20: warning: unused variable 'rgt' [-Wunused-variable]
   20 |     int i, j, lft, rgt;
      |                    ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...