Submission #18040

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

interval

#define _CRT_SECURE_NO_WARNINGS
      
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
      
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

char S[1505], T[1505];
int N, M;

int main() {
	scanf("%s%s", S, T);
	N = strlen(S);
	M = strlen(T);

	if(N > M) {
		swap(S, T);
		swap(N, M);
	}

	for(int i = 0; i < N; i++) S[i] -= 'a';
	for(int i = 0; i < M; i++) T[i] -= 'a';

	for(int len = N; len >= 1; len--) {
		set< vector<int> > Q;
		{
			vector<int> c(26);
			for(int j = 0; j < len-1; j++) c[S[j]]++;
			for(int i = 0, j = len-1; j < N; i++, j++) {
				c[S[j]]++;
				Q.insert(c);
				c[S[i]]--;
			}
		}
		{
			vector<int> c(26);
			for(int j = 0; j < len-1; j++) c[T[j]]++;
			for(int i = 0, j = len-1; j < M; i++, j++) {
				c[T[j]]++;
				if(Q.find(c) != Q.end()) {
					printf("%d\n", len);
					return 0;
				} 
				c[T[i]]--;
			}
		}
	}

	puts("0");
    return 0;
}

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