| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 274844 | sean9892 | 구간 성분 (KOI15_interval) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
using pii=pair<ll,ll>;
ll ga[1510];
ll ha[1510];
ll gb[1510];
ll hb[1510];
set<pii> s;
ll p7[30];
ll p5[30];
const ll mod=9223372036854775783ll;
int res=0;
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
{
ll a=1,b=1;
for(int i=0;i<26;i++){
p7[i]=a;
p5[i]=b;
a*=7;
b*=5;
a%=mod;
}
}
string a,b;
cin>>a>>b;
if(a.size()>b.size())swap(a,b);
ga[0]=gb[0]=ha[0]=hb[0]=0;
ga[1]=p7['z'-a[0]];
ha[1]=p5[a[0]-'a'];
for(int i=1;i<a.size();i++){
ga[i+1]=ga[i]+p3['z'-a[i]];
ha[i+1]=ha[i]+p5[a[i]-'a'];
}
gb[1]=p7['z'-b[0]];
hb[1]=p5[b[0]-'a'];
for(int i=1;i<b.size();i++){
gb[i+1]=gb[i]+p3['z'-b[i]];
hb[i+1]=hb[i]+p5[b[i]-'a'];
}
if(10ll*a.size()*a.size()*b.size()<=2e9){
for(int i=1;i<a.size();i++){
for(int j=0;j+res<i;j++){
for(int k=i-j;k<b.size();k++){
if(ha[i]-ha[j]==hb[k]-hb[k-i+j]){
res=max(res,i-j);
break;
}
}
}
}
cout<<res;
return 0;
}
for(int i=(int)a.size()-1;i>0;i--){
for(int j=0;j<i;j++){
ll x=ga[i]-ga[j];
ll y=ha[i]-ha[j];
s.insert(pii(x,y));
}
}
for(int i=(int)a.size()-1;i>0;i--){
for(int j=0;j+res<i;j++){
ll x=gb[i]-gb[j];
ll y=hb[i]-hb[j];
if(s.find(pii(x,y))!=s.end()){
res=max(res,i-j);
break;
}
}
}
cout<<res;
}