[Python] 7575번: 바이러스

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

7575번: 바이러스

 

import sys
input = sys.stdin.readline


def get_pi(keyword):
    keyword_length = len(keyword)
    pi = [0]*keyword_length
    j = 0

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

        if keyword[i] == keyword[j]:
            j += 1
            pi[i] = j

    return pi


def it_there_one_keyword(string, keyword, pi):
    string_length = len(string)
    i, j = 0, 0

    while i < string_length:
        if string[i] == keyword[j]:
            i += 1
            j += 1
        else:
            if j == 0:
                i += 1
            else:
                j = pi[j-1]

        if j == K:
            return True

    return False


def has_virus():
    for i in range(K, len(info[0])+1):
        # Set target
        cur_str = info[0][i-K:i]
        cur_str_reversed = list(reversed(cur_str))

        # Search
        flag = True
        pi = get_pi(cur_str)
        pi_reversed = get_pi(cur_str_reversed)

        for j in range(1, N):
            result1 = it_there_one_keyword(info[j], cur_str, pi)
            result2 = it_there_one_keyword(info[j], cur_str_reversed, pi_reversed)

            if result1 == False and result2 == False:
                flag = False
                break

        # If keyword was searched in every other strings
        if flag:
            return True

    return False


if __name__ == '__main__':
    N, K = map(int, input().split())

    info = []
    for _ in range(N):
        _ = int(input())
        info.append(list(map(int, input().split())))

    if(has_virus()):
        print("YES")
    else:
        print("NO")

 

has_virus()가 메인 로직입니다. 가장 바깥 for문은 첫번째 프로그램을 기준으로, K자씩 가져오기 위함입니다. 예를 들어, K = 4이고, 첫 프로그램이 abcde이면 abcd, bcde 순서로 접근합니다. cur_str, cur_str_reversed에 해당 문자열과 뒤집힌 문자열을 가져옵니다.

다음으로 검색을 시도합니다. 빠른 검색을 위해 KMP 알고리즘을 사용합니다. 다만, 이전에 설명한 적이 있으므로 설명을 생략하고, 관련 링크로 대체합니다.

 

https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-1893%EB%B2%88-%EC%8B%9C%EC%A0%80-%EC%95%94%ED%98%B8

[Python] 백준 1893번: 시저 암호

 

2개의 문자열에 대한 pi 테이블을 함수를 통해 가져옵니다.

다음으로 반복문을 수행합니다. 이것의 목적은, 1번째 프로그램을 제외한 모든 프로그램에 현재 문자열 2개 중에 1개라도 모두 포함하는지를 검사하는 것입니다. 즉 문제에서 설명한 것처럼, 현재 문자열이 현재 모든 프로그램에 나타나는지를 KMP를 통해 검색합니다.

이렇게 나머지 프로그램들에 대해 검색을 하였는데, 모든 프로그램에서 문자열이 검색되었을 경우 flag 값이 True를 가리키게 됩니다. 이 경우 has_virus() 함수는 True를 반환합니다.

 

마지막으로, 이 함수의 결과에 따라 YES, NO를 출력해주면 됩니다.