Problem E : 구간 성분

Problem E : 구간 성분

 

제한시간: 1000 ms    메모리제한: 256 MB

 

 

매 초마다 신호를 발생시키는 두 장치 A, B가 있다. 이 신호는 알파벳 소문자의 서열로 표현된다.
A, B로 부터 발생한 신호를 서열로 표시한 SA, SB의 예는 다음과 같다.

 

SA = [ a, f, c, d, r, d, e, s, d, e, f, w, s, z, r ]
SB = [ g, e, d, s, r, d, d, e, m, z, r ]

 

신호 서열의 어떤 구간에 포함된 문자의 종류와 개수가 순서에 상관없이 동일하면 이 두 ‘구간의성분’은 같다고 한다. 

아래에서 박스로 표시된 부분은 두 신호 SA, SB에서 성분이 같은 구간을 나타내고 있다.

 

 

 

즉 위의 예와 같이 성분이 같은 구간의 길이는 두 서열에서 반드시 같아야 한다. 그리고 같은 성분의 구간은 하나 이상 존재할 수 있다. 

우리는 두 신호 서열에 각각 존재하는 같은 성분 구간 중에서 가장 긴 것을 찾으려고 한다.

표준 입력으로 다음의 정보가 주어진다. 첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다. 이 문자열은 영문 소문자로만 구성되어 있다. 두 입력 문자열의 크기 N,M 의 범위는 5≤N,M≤1,500이다.

표준 출력으로 두 서열에서 같은 성분을 가진 구간 중에서 가장 긴 구간을 찾아, 그 구간의 길이를 출력해야 한다. 부분문제의 제약 조건 • 부분문제 1: 전체 점수 100점 중 7점에 해당하며 N,M≤100 이다. • 부분문제 2: 전체 점수 100점 중 23점에 해당하며 N,M≤500 이다. • 부분문제 3: 전체 점수 100점 중 31점에 해당하며 N,M≤1,000 이다. • 부분문제 4: 전체 점수 100점 중 39점에 해당하며 N,M≤1,500 이다.

 

xraphy

edgeedgem

 

0 

 

afcdrdesdefwszr

gedsrddemzr

 

7

 

computersystem

sesystuercomplexity

 

11

 

#include <stdio.h>
#include <string.h>
#define MOD 10000

#define MAX 16 // 1510
char A[MAX], B[MAX];
int asum[MAX], bsum[MAX], alen, blen, bn;

struct data {
	int pos;
	data *next;
	data *myAlloc(int _pos, data *_next) {
		pos = _pos, next = _next;
		return this;
	}
} *hash[MOD], buf[1510];

void push(int key, int pos)
{
	hash[key] = buf[bn++].myAlloc(pos, hash[key]);
}

int Min(int x, int y) { return x < y ? x : y; }

int match(int len, int apos, int bpos) // cnt 숫자가 동일한지 확인함
{
	int cnt[30] = { 0 }, i;
	for (i = 0; i < len; i++) {
		cnt[A[apos - i] - 97]++;
		cnt[B[bpos - i] - 97]--;
	}
	for (i = 0; i < 26; i++) if (cnt[i] != 0) return 0; // 안맞음
	return 1; // 맞음
}

int find(int len)
{
	int i, key;
	bn = 0;
	for (i = 0; i < MOD; i++) hash[i] = 0; // 하나의 길이에 대해서 초기화를 하고
	for (i = len; i <= alen; i++) {
		push((asum[i] - asum[i - len]) % MOD, i); //  a 문자열에 대해 해시값을 만들음
	}
	for (i = len; i <= blen; i++) {
		key = (bsum[i] - bsum[i - len]) % MOD;
		for (data *p = hash[key]; p != 0; p = p->next) {
			if (match(len, p->pos, i)) return 1; // b 문자열에서 찾음
		}
	}
	return 0;
}

int main()
{
	freopen("input.txt", "r", stdin);
	int i;
	scanf("%s %s", A + 1, B + 1);
	alen = strlen(A + 1), blen = strlen(B + 1);
	for (i = 1; i <= alen; i++){
		asum[i] = asum[i - 1] + (A[i] - 96) * (A[i] - 96); // 해시값 만들기 전 전처리
	}
	for (i = 1; i <= blen; i++) {
		bsum[i] = bsum[i - 1] + (B[i] - 96) * (B[i] - 96); // 동일
	}

	for (i = Min(alen, blen); i > 0; i--) { // 긴 길이 부터 넣음
		if (find(i)) break;
	}
	printf("%d\n", i); // 긴것부터 해서 줄여나감
	return 0;
}