[백준/BOJ] 11478번 서로 다른 부분 문자열의 개수 (C/C++)

백준 온라인 저지(BOJ) 11478번 서로 다른 부분 문자열의 개수
https://www.acmicpc.net/problem/11478

11478번: 서로 다른 부분 문자열의 개수

* 사용언어 : C언어, C++
 

1. 문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 출력
부분 문자열은 S에서 연속된 일부분을 말함 (길이는 1보다 크거나 같음)

 

2. 풀이

우선 문자열 내의 모든 부분 문자열을 탐색해야 합니다.
2중 for문을 활용하여 ① 길이를 1부터 sLen(문자열의 길이)까지 순서대로 순회하면서,
② 해당 길이의 모든 부분 문자열을 탐색했습니다.
 
각 부분 문자열은 개별 문자열로 보고 hash table에 모두 기록하였습니다.
hash table에 입력할 때 중복이 있으면 기록하지 않고 그대로 함수를 return 했고
처음 기록하는 경우라면 출력 변수(res)를 1 증가시켰습니다.
 
처음에 모든 부분 문자열을 담기 위해 hash table의 크기를 500,500 * 3배로 했다가
메모리 초과가 발생했습니다. (1부터 1,001까지의 합 + hash 충돌 고려 3배)
 

여기서 고민을 많이 했는데
길이 별 부분 문자열이 최대 1,000개라는 것을 깨닫고
hash table의 사이즈를 1,000개 기준으로 하향 조정했습니다.
 
대신 전체 부분 문자열(500,500개)을 처리하기 위한 추가 조치가 필요했는데,
저는 hash table에 문자열이 길이가 1부터 sLen까지 순차적으로 들어오는 것을 이용하여
아래와 같이 하나의 hash table로 처리할 수 있도록 add 함수를 약간만 수정했습니다. (문자열 idx 활용)

void h_add(const char* s, int idx) {
	// 생략
	while (HT[h][idx] && cnt--) { // idx번 자리가 비어있으면 빈칸 취급
		if (!my_strcmp(s, HT[h])) return; // 같은 문자열이 있으면 return (중복)
		h = (h + 1) % HLM; // open addressing
	}
	// 생략
}

스스로 고민한 결과로 ① 메모리 절약, ② 간결한 코드를 모두 달성한 것 같아서
백준 문제를 풀면서 오랜만에 꽤 만족스러운 경험이 되었습니다.
 
기타 풀이는 아래 코드로 설명 대체하겠습니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11478_서로 다른 부분 문자열의 개수
4076KB	832ms
*/
#include <cstdio>

const int CLM = 1005;
const int HLM = CLM * 3;

char HT[HLM][CLM], s[CLM], subS[CLM];
int sLen, res;

int my_strlen(const char* a) {
	int len = 0;
	while (*a++) ++len;
	return len;
}

int my_strcmp(const char* a, const char* b) {
	while (*a && *b && *a == *b) *a++, *b++;
	return *a - *b;
}

void my_strncpy(const char* src, char* des, int len = CLM) {
	int n = 0;
	while (*src && n++ < len) *des++ = *src++;
	*des = 0;
}

int hash(const char* s) {
	unsigned long int hash = 5381;
	int c;
	while (c = *s++) hash = (((hash << 5) + hash) + c) % HLM;
	return hash % HLM;
}

void h_add(const char* s, int idx) {
	int h = hash(s);
	int cnt = HLM;
	while (HT[h][idx] && cnt--) {
		if (!my_strcmp(s, HT[h])) return;
		h = (h + 1) % HLM;
	}
	my_strncpy(s, HT[h]);
	++res;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%s", s);
	sLen = my_strlen(s);
	for (int i = 1; i <= sLen; ++i) {
		for (int j = 0; j <= sLen - i; ++j) {
			my_strncpy(&s[j], subS, i);
			h_add(subS, i - 1);
		}
	}

	printf("%d\n", res);
	return 0;
}