# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
348013 | elizarv | Necklace (Subtask 4) (BOI19_necklace4) | C++14 | 247 ms | 620 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T a,Args... args) {cout<<a<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define SZ(x) int(x.size())
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
vector<int> prefix_function(string &s) {
int n = s.size();
vector<int> pf(n);
pf[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
while (j && s[i] != s[j]) j = pf[j-1];
if (s[i] == s[j]) j++;
pf[i] = j;
}
return pf;
}
vector<int> kmp(string &s, string &p) {
int n = s.size(), m = p.size(), cnt = 0;
vector<int> mx(n, 0);
if(!m)return mx;
vector<int> pf = prefix_function(p);
for(int i = 0, j = 0; i < n; i++) {
while(j && s[i] != p[j]) j = pf[j-1];
if(s[i] == p[j]) j++;
mx[i] = j;
if(j == m) {
cnt++;
j = pf[j-1];
}
}
return mx;
}
int ans, a, b;
void go(string &s, string &t, bool f = false){
int n = s.size();
int m = t.size();
string rev = t;
reverse(rev.begin(), rev.end());
forn(i, 0, n){
string lf = s.substr(0, i);
string rg = s.substr(i, n-i);
reverse(lf.begin(), lf.end());
vector<int> suf = kmp(rev, lf);
vector<int> pref = kmp(t, rg);
reverse(suf.begin(), suf.end());
forn(j, 0, m){
if(pref[j] + j < m){
int aux = pref[j] + suf[j+1];
if(ans < aux){
ans = aux;
if(f){
a = m - i - pref[j];
b = j - pref[j] - 1;;
}else{
a = i - suf[j+1];
b = j - pref[j] + 1;
}
}
}
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
string s, t;
cin >> s >> t;
go(s, t);
reverse(t.begin(), t.end());
go(s, t, true);
cout << ans << endl;
cout << a << " " << b << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |