Submission #18096

#	Time	Username	Problem	Language	Result	Execution time	Memory
18096		comet	구간 성분 (KOI15_interval)	C++14	100 / 100	525 ms	1348 KiB

interval

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
using namespace std;

char t[2][1510];

int main(){

	int sz[2];
	for(int i=0;i<2;i++){
		scanf("%s",t[i]);
		sz[i]=strlen(t[i]);
	}

	int n=min(sz[0],sz[1]);

	for(int i=n;i>0;i--){
		vector<char> s(30);
		set<vector<char>> S;
		for(int j=0;j<i;j++){
			s[t[0][j]-'a']++;
		}
		S.insert(s);
		for(int j=0;j<sz[0]-i;j++){
			s[t[0][j]-'a']--;
			s[t[0][j+i]-'a']++;
			S.insert(s);
		}

		s=vector<char>(30);
		for(int j=0;j<i;j++){
			s[t[1][j]-'a']++;
		}
		if(S.find(s)!=S.end()){
				printf("%d\n",i);
				return 0;
		}
		for(int j=0;j<sz[1]-i;j++){
			s[t[1][j]-'a']--;
			s[t[1][j+i]-'a']++;
			if(S.find(s)!=S.end()){
				printf("%d\n",i);
				return 0;
			}
		}
	}
	puts("0");
	return 0;
}

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