Submission #18466

#	Time	Username	Problem	Language	Result	Execution time	Memory
18466		eaststar	구간 성분 (KOI15_interval)	C++14	100 / 100	516 ms	1716 KiB

interval

#include <stdio.h>
#include <string.h>
#include <set>
#include <vector>
using namespace std;
vector<int> t(26);
set<vector<int> > s;
char a[1510],b[1510];
int main(){
    int i,j,n,m;
    scanf("%s\n%s",a,b);
    n=strlen(a);
    m=strlen(b);
    for(i=min(n,m);i;--i){
        for(j=0;j<26;++j)t[j]=0;
        for(j=0;j<i-1;++j)++t[a[j]-97];
        for(j=i-1;j<n;++j){
            ++t[a[j]-97];
            s.insert(t);
            --t[a[j-i+1]-97];
        }
        for(j=0;j<26;++j)t[j]=0;
        for(j=0;j<i-1;++j)++t[b[j]-97];
        for(j=i-1;j<m;++j){
            ++t[b[j]-97];
            if(s.find(t)!=s.end()){
                printf("%d",i);
                return 0;
            }
            --t[b[j-i+1]-97];
        }
        s.clear();
    }
    puts("0");
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39