[코딩테스트][백준] 🔥 백준 1786번 "찾기" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 30분

def create_pi_table(pattern):
    table=[0 for _ in range(len(pattern))]
    i=0
    for j in range(1,len(pattern)):
        while i>0 and pattern[i]!=pattern[j]:
            i=table[i-1]
        if pattern[i]==pattern[j]:
            i+=1
            table[j]=i
    return table

def kmp(all_string,pattern):
    table=create_pi_table(pattern)

    # kmp
    i=0
    result=[]
    for j in range(len(all_string)):
        while i>0 and pattern[i]!=all_string[j]:
            i=table[i-1]

        if pattern[i]==all_string[j]:
            i+=1
            if i==len(pattern):
                result.append(j-i+2)
                i=table[i-1]
    return result

s=input()
t=input()
result=kmp(s,t)
print(len(result))
print(*result)

KMP 알고리즘의 설명을 해주면서 KMP 알고리즘을 쓰기를 요구하는 문제이다. KMP 알고리즘에 대해서는 따로 정리해두었다. 단순히 알고리즘의 결과를 출력 결과로 내보내면 된다.

이렇게 Python으로 백준의 "찾기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊