# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
992159 | Catas | Necklace (Subtask 4) (BOI19_necklace4) | C++14 | 183 ms | 604 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long int
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rep(b) for(ll i = 0; i<b; i++)
#define repn(a, b) for(ll b = 0; i<a; i++)
#define LSOne(S) (S & -(S))
#define mem(a, b) memset(a, b, sizeof(a))
#define MOD 1000000007ll
#define MAXN 6002
using namespace std;
void suffix_array(string const& s, vector<ll>& p, vector<ll>& lcp) {
int n = s.size();
const int alphabet = 256;
vector<int> c(n), cnt(max(alphabet, n), 0);
for (int i = 0; i < n; i++)
cnt[s[i]]++;
for (int i = 1; i < alphabet; i++)
cnt[i] += cnt[i-1];
for (int i = 0; i < n; i++)
p[--cnt[s[i]]] = i;
c[p[0]] = 0;
int classes = 1;
for (int i = 1; i < n; i++) {
if (s[p[i]] != s[p[i-1]])
classes++;
c[p[i]] = classes - 1;
}
vector<int> pn(n), cn(n);
for (int h = 0; (1 << h) < n; ++h) {
for (int i = 0; i < n; i++) {
pn[i] = p[i] - (1 << h);
if (pn[i] < 0)
pn[i] += n;
}
fill(cnt.begin(), cnt.begin() + classes, 0);
for (int i = 0; i < n; i++)
cnt[c[pn[i]]]++;
for (int i = 1; i < classes; i++)
cnt[i] += cnt[i-1];
for (int i = n-1; i >= 0; i--)
p[--cnt[c[pn[i]]]] = pn[i];
cn[p[0]] = 0;
classes = 1;
for (int i = 1; i < n; i++) {
pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
if (cur != prev)
++classes;
cn[p[i]] = classes - 1;
}
c.swap(cn);
}
int k = 0;
for(int i = 0; i < n-1; i++){
int pi = c[i];
int j = p[pi-1];
while(s[i+k] == s[j+k]) k++;
lcp[pi] = k;
k = max(k-1, 0);
}
}
int pi1[MAXN], pi2[MAXN];
void kmp(string s, int* pi){
pi[0] = 0;
int len = 0, j = 1, m = s.size();
while(j<m){
if(s[j] == s[len]){
pi[j] = ++len;
j++;
}
else{
if(len) len = pi[len-1];
else{
pi[j] = 0;
j++;
}
}
}
}
void solution(string s, string t, vector<int>& ans, bool rev){
int n = s.size(), m = t.size();
for(int i = 0; i < n; i++){
string s1 = s.substr(0, i), s2 = s.substr(i, n-i);
reverse(s1.begin(), s1.end());
string t1 = t, t2 = t;
reverse(t2.begin(), t2.end());
kmp(s1 + "#" + t1, pi1); kmp(s2 + "#" + t2, pi2);
for(int j = 1; j<=m; j++){
if(pi1[i + j] + pi2[n + m - i - j] > ans[0]){
ans[0] = pi1[i+j] + pi2[n+m-i-j];
ans[1] = i - pi1[i+j];
ans[2] = rev ? m - j - pi2[n+m-i-j] : j - pi1[i+j];
}
}
}
}
void solve(){
string s, t;
cin>>s>>t;
vector<int> ans(3, 0);
solution(s, t, ans, 0);
reverse(t.begin(), t.end());
solution(s, t, ans, 1);
cout<<ans[0]<<'\n'<<ans[1]<<' '<<ans[2]<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t = 1;
//cin>>t;
while(t--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |