2 Problem E : 구간 성분

두 문자열에서 같은 성분을 가진 구간 중에서 가장 긴 구간을 찾아, 그 구간의 길이를 출력하는 프로그램

- 해싱

- 정적 할당

- 해싱 키 값을 만드는 과정

- 완전 탐색에서, 해싱 키 값을 규칙에 의해서 만들어 냄

 

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

char A[1510], B[1510];
int asum[1510], bsum[1510], 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)
{
	int cnt[30] = { 0 }, i;
	for (i = 0; i < len; i++) {
		cnt[A[apos - i] - 97]++; // 알파벳 보고 cnt
		cnt[B[bpos - i] - 97]--;
	}
	for (i = 0; i < 26; i++) if (cnt[i] != 0) return 0; // 짝이 맞지 않으면 실패
	return 1; // 모두 0으로 짝이 맞으면 성공
}

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); // 키값을 만들어 내는 규칙
	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;
		}
	}
	return 0;
}

int main()
{
	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;
}

xraphy edgeedgem	0
afcdrdesdefwszr gedsrddemzr	7
computersystem sesystuercomplexity	11