Submission #71128

#TimeUsernameProblemLanguageResultExecution timeMemory
711283zp구간 성분 (KOI15_interval)C++14
61 / 100
1084 ms46500 KiB
#include<bits/stdc++.h> using namespace std; int A = 987654323; int B = 1e9 + 9; int C = 985201597; int D = 660353359; int pol1[26]; int pol2[26]; set<pair<int,int> > sa[1509]; main(){ pol1[0] = 1; for(int i = 1; i < 26; i ++) pol1[i] = (long long)pol1[i - 1] * (long long)A % B; pol2[0] = 1; for(int i = 1; i < 26; i ++) pol2[i] = (long long)pol2[i - 1] * (long long)C % D; int n, m; string a, b; cin >> a >> b; n = a.size(), m = b.size(); for(int i = 0; i < n; i++){ int H1 = 0, H2 = 0; for(int j = i; j < n; j++){ H1 += pol1[a[j] - 'a']; H2 += pol2[a[j] - 'a']; if(H1 >= B) H1 -= B; if(H2 >= D) H2 -= D; sa[j - i + 1].insert({H1,H2}); } } int ans = 0; for(int i = 0; i < m; i++){ int H1 = 0, H2 = 0; for(int j = i; j < m; j++){ H1 += pol1[b[j] - 'a']; H2 += pol2[b[j] - 'a']; if(H1 >= B) H1 -= B; if(H2 >= D) H2 -= D; if(sa[j - i + 1].find({H1,H2}) != sa[j - i + 1].end()){ ans = max(ans, j - i + 1); } } } cout << ans << endl; }

Compilation message (stderr)

interval.cpp:10:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...