[백준][문자열] 찾기

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/1786

1786번: 찾기

 

내가 작성한 코드

import sys

read = sys.stdin.readline

def get_data():
    T = read().rstrip()
    P = read().rstrip()
    return T, P

def get_pi(p):
    m = len(p)
    pi = [0] * m

    j = 0
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = pi[j-1]
        if p[i] == p[j]:
            j += 1
            pi[i] = j
    return pi

def kmp(s, p):
    n, m = len(s), len(p)
    pi = get_pi(p)
    ans = []

    j = 0
    for i in range(n):
        while j > 0 and s[i] != p[j]:
            j = pi[j-1]
        if s[i] == p[j]:
            if j == m-1:
                ans.append(i-m+1)
                j = pi[j]
            else:
                j += 1
    return ans

T, P = get_data()
ans = kmp(T, P)
print(len(ans))
for i in ans:
    print(i+1)

• KMP 알고리즘
  
  • KMP 알고리즘으로 바로 풀 수 있는 문제
  • KMP 알고리즘에 대해 이해하는 것이 중요함
  • 아래 블로그에서 매우 자세히 설명해주심

https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

 

다른 사람이 작성한 코드

def make_pi():
    pi = [0 for i in range(0, len(P))]

    j = 0
    for i in range(1, len(P)):
        while j > 0 and P[i] != P[j]:
            j = pi[j - 1]

        if (P[i] == P[j]):
            j += 1
            pi[i] = j
    return pi


def solution(pi):
    result = []
    count = 0

    j = 0
    for i in range(0, len(T)):

        while j > 0 and T[i] != P[j]:
            j = pi[j - 1]

        if T[i] == P[j]:
            if j == (len(P) - 1):
                result.append(i - len(P) + 2)
                count += 1
                j = pi[j]
            else:
                j += 1

    print(count)
    for element in result:
        print(element)


T = input()
P = input()
solution(make_pi())

• 대부분 일치하는 코드다

https://donghak-dev.tistory.com/60

[알고리즘][Python] 백준 1786 찾기 문제 풀이

 

기억해야할 것

• KMP 알고리즘의 이해
  
  • 알고리즘 코드만 보면 쉽게 해결할 수 있음
  • 그러나 알고리즘을 정확하게 이해하는 것이 중요함