이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int INF = 1LL<<60;
string a;
string b;
int n,m;
vector<vector<int>> match;
vector<vector<int>> smallest;
vector<pair<int,int>> solve() {
match=vector<vector<int>>(n,vector<int>(m,0));
smallest=vector<vector<int>>(n+1,vector<int>(m+1,INF));
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
int ct=0;
for (int t=0; t<min(n-i, m-j); t++) {
if (a[i+t]!=b[j+t]) {
break;
}
ct++;
}
match[i][j] = ct;
}
}
for (int x=0; x<n; x++) {
for (int t=0; t<m; t++) {
for (int r=t; r<=t+match[x][t]; r++) {
smallest[x][r] = min(smallest[x][r],t);
}
}
}
int ans = 0;
pair<int,int> xpos,ypos;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
int M = match[i][j];
int x = i+M;
int tau = smallest[x][j];
//cout << i << " " << j << " " << M <<" " << x << " " << tau << endl;
if (tau==INF) {
continue;
}
int subans = j-tau+M;
if (subans>ans) {
xpos={i,i+subans-1};
ypos={tau,j+M-1};
}
ans=max(ans,subans);
}
}
//cout << a <<" " << b <<" " << ans <<" " << ans <<" " << xpos.first <<" " << xpos.second <<" " << ypos.first <<" " << ypos.second << endl;
return {{ans,ans},xpos,ypos};
}
signed main() {
//freopen("input.txt","r", stdin);
//freopen("output.txt","w",stdout);
cin >> a;
cin >> b;
n=a.size();
m=b.size();
vector<pair<int,int>> ans2;
vector<int> ans(3);
ans2=solve();
ans[0] = ans2[0].first;
ans[1] = ans2[1].first;
ans[2] = ans2[2].first;
reverse(b.begin(), b.end());
ans2 = solve();
if (ans2[0].first>ans[0]) {
ans[0] = ans2[0].first;
ans[1] = ans2[1].first;
ans[2] = m-ans2[2].second-1;
}
reverse(a.begin(), a.end());
ans2 = solve();
if (ans2[0].first>ans[0]) {
ans[0] = ans2[0].first;
ans[1] = n-ans2[1].second-1;
ans[2] = m-ans2[2].second-1;
}
reverse(b.begin(), b.end());
ans2 = solve();
if (ans2[0].first>ans[0]) {
ans[0] = ans2[0].first;
ans[1] = n-ans2[1].second-1;
ans[2] = ans2[2].first;
}
cout << ans[0] << endl;
cout << ans[1] <<" " << ans[2] << endl;
//want to store for each x and j, the smallest t such that match[x][t]+t = j
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |