[백준] 14425. 문자열_문자열집합 - Python

문제

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

 

-----------------------------------------------------------------------------------------------------------------------------------

★ 시작하기 전에

간단하게 풀 수 있는 문제이다.

물론, 나는 또 어렵게 풀려 했다. 문제를 잘못 이해했기 때문...

집합 S 내의 문자와 주어진 문자열이 완전히 일치하는 것이 아닌, 포함하고 있다고 생각했다.

그래서 보이어 무어 알고리즘을 활용하여 문자열 찾기를 시도했다..

def find(start, check_dot ,alpha, x, y):
    cnt = 1
    for k in range(start+1, x-(y-1-check_dot)):
        if ele[k] == alpha:
            return cnt
        cnt += 1
    return cnt

def bm(ele, check):
    x = len(ele)
    y = len(check)

    # ele에서 시작점 : 변경될것이다.
    a = 0
    while a <= x-y:
        # check할 단어의 시작점(맨 뒤부터)-
        b = y-1

        while b>=0:
            if check[b] != ele[a+b]:
                change = find(a+b, b, check[b], x, y)
                break
            b -= 1
        if b == -1:
            return True
        else:
            a += change
    return False

ans = 0
for j in range(m):
    check = input()
    for ele in data:
        if bm(ele, check):
            ans += 1
print(ans)

하지만... 절대 이렇게 푸는 것이 아니라 일치하는 간단한 문제!

물론 위에 보이어무어도 제대로된 코드같지는 않지만 다시 한번 보이어 무어 알고리즘을 생각해볼 수 있었다.

http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf

출처: https://snupi.tistory.com/2 [SNUPI]

 

위 참조를 틈틈히 생각 안나면 보자!

 

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

data = [0 for _ in range(n)]
for i in range(n):
    data[i] = input()
ans =0
for j in range(m):
    check = input()
    if check in data:
        ans+=1
print(ans)

이렇게 간단히 구현 가능하다. by python