Submission #18417

#TimeUsernameProblemLanguageResultExecution timeMemory
18417suhgyuho_william구간 성분 (KOI15_interval)C++98
61 / 100
789 ms131072 KiB
#include <stdio.h> #include <string.h> #include <algorithm> #include <map> using namespace std; int N,M; int a[1510],b[1510],tmp[1510]; char s[1510]; struct data{ int cnt; int a[26]; bool operator<(const data x)const{ int i; if(x.cnt != cnt) return cnt < x.cnt; for(i=0; i<26; i++){ if(x.a[i] != a[i]) return a[i] < x.a[i]; } return false; } }cnt1[1510],cnt2[1510]; data t; map<data,bool> Map; int main(){ int i,j,k; //freopen("input.txt","r",stdin); scanf("%s",s); N = strlen(s); for(i=1; i<=N; i++) a[i] = s[i-1]-'a'; scanf("%s",s); M = strlen(s); for(i=1; i<=M; i++) b[i] = s[i-1]-'a'; if(N < M){ for(i=1; i<=N; i++) tmp[i] = a[i]; for(i=1; i<=M; i++) a[i] = b[i]; for(i=1; i<=N; i++) b[i] = tmp[i]; swap(N,M); } for(i=1; i<=N; i++){ for(j=0; j<26; j++) cnt1[i].a[j] = cnt1[i-1].a[j]; cnt1[i].a[a[i]]++; } for(i=1; i<=M; i++){ for(j=0; j<26; j++) cnt2[i].a[j] = cnt2[i-1].a[j]; cnt2[i].a[b[i]]++; } for(i=1; i<=M; i++){ for(j=i; j<=M; j++){ for(k=0; k<26; k++) t.a[k] = (cnt2[j].a[k]-cnt2[i-1].a[k]); t.cnt = j-i+1; Map[t] = true; } } for(i=N-1; i>=0; i--){ for(j=1; j+i<=N; j++){ for(k=0; k<26; k++) t.a[k] = (cnt1[j+i].a[k]-cnt1[j-1].a[k]); t.cnt = i+1; if(Map.find(t) != Map.end()){ printf("%d",i+1); return 0; } } } printf("0"); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...