[ BOJ ] 1543 : 문서 검색 ( SILVER 5 ) / C, Python

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

풀이 과정

문서를 처음부터 끝까지 검토하면서, 만약 문서의 특정 글자가 검색하고 싶은 단어의 첫 번째 글자가 일치한다면, 검색하고 싶은 단어와 똑같은 단어가 문서에 존재하는지 확인한다. (Exact Match) 문서 범위를 오버하여 검색하는 것을 유의하고, 공백으로 이루어져있다는 것도 유의하자.

C

#include <stdio.h>
#include <string.h>

char original[50005] = {0,};
int o_len = 0;
char search[50005] = {0,};
int s_len = 0;
int main(void) {
    gets(original);
    o_len = strlen(original);
    gets(search);
    s_len = strlen(search);

    int result = 0;
    for (int i = 0; i < o_len - s_len + 1; i++) {
        if (original[i] == search[0]) {
            int done = 1;
            for (int j = 0; j < s_len; j++) {
                if (original[i+j] != search[j]) {
                    done = 0;
                    break;
                }
            }

            if (done == 1) {
                result += 1;
                i += s_len - 1;
            }
        }
    }

    printf("%d", result);
    return 0;
}

문자열의 길이를 미리 변수에 저장해놓고 시작하자. strlen() 을 자주 사용하면 OutOfBounds 오류가 난다. ( 이유는 모르지만 반복되는 문자열 길이 구하기는 시간상 좋지 않으니 미리 변수에 저장해놓고 사용하는 것이 좋다. )

Python

import sys
input = sys.stdin.readline

original = input().rstrip()
source = input().rstrip()

idx = 0
cnt = 0
while idx < len(original):
    if original[idx] == source[0]:
        if original[idx:idx+len(source)] == source:
            cnt += 1
            idx += len(source) - 1
    
    idx += 1
print(cnt)