Easy is Perfect

[백준] 11478번 C/C++ 풀이 _ 서로 다른 부분 문자열의 개수

  • melonicedlatte
  • Aug 12, 2018


출처 : https://www.acmicpc.net/problem/11478 

서로 다른 부분 문자열의 개수 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초256 MB82335426051.485%

문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

출력

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

예제 입력 1 

ababc

예제 출력 1 

12

출처

알고리즘 분류

풀이

문자열의 길이가 최대 1000이기 때문에, 가능한 부분 문자열은 아래와 같습니다. 
1자리 : 1000-0   개
2자리 : 1000-1   개
3자리 : 1000-2   개
4자리 : 1000-3   개
......
1000자리 : 1000 - 999 개 

총합 : 1부터 1000까지의 합 = (1000)(1000+1)/2 = 500500


1자리 글자부터 최대 글자 까지 전부  set에 넣어주면 자동으로 중복을 제거합니다. 
c언어의 set 은 이진트리를 사용하고, 알고리즘으로 O(nlogn) 의 정렬 복잡도를 가지기 때문에 500500 * log(500500) 으로
기준 시간 내에 풀이가 가능합니다. 

https://algoshipda.blogspot.com/2017/05/boj-11478.html 링크를 참조하면 3가지 풀이가 존재한다고 합니다. 
다른 풀이도 익혀두는 것이 좋을 것 같습니다!

길이 N인 문자열 S의 서로 다른 부분 문자열의 개수를 세는 문제이다.

방법 1) Suffix Array + LCP
O(NlgN)에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다.

방법 2) 트라이
O(N2)에 해결할 수 있다. 트라이에 S의 N(N+1)2개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다.

방법 3) 해싱
O(N2lgN)에 해결할 수 있다. S의 N(N+1)2개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다.

코드 (트라이) : http://ideone.com/bugbDy 
코드 (해싱) : http://ideone.com/hkjw5n

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string.h>
#include <set>
using namespace std;
#pragma warning(disable : 4996)
 
// global
#define MAX_LEN 1000 + 1 
 
// main 
int main() {
    // init 
    set<string> string_set; 
    char input_str[MAX_LEN];
    scanf("%s", input_str);
    int input_str_len = strlen(input_str);
 
    // string 을 1~글자 수 만큼 쪼개서 set에 넣어준다. 
    for (int part_str_len = 1; part_str_len <= input_str_len; part_str_len++) {
        for (int part_idx = 0; part_idx < input_str_len - part_str_len+1; part_idx++) {
            int start_idx = part_idx;
            int end_idx = part_idx + part_str_len;
            string sub_string(input_str+ start_idx, input_str + end_idx) ;
            string_set.insert(sub_string);
        }
    }
 
    cout << string_set.size();
 
    return 0; 
}
cs



Search