LeetCode - Number of Subarrays That Match a Pattern II

https://leetcode.com/problems/number-of-subarrays-that-match-a-pattern-ii/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문자열에서 패턴을 찾는 문제이다.

 

기존에 알고 있던 내용은

 

찾을 패턴 : AABA

문자열 : AABABAACA

가 있다고 할때

 

A A B A B A A C A

A A B A

   A A B A

      A A B A

         A A B A

 

방식으로

O(NM)만큼 걸리는 방법을 이용했다.

그러면 시간초과로 문제를 풀 수 없어서 찾은 방법이

 

KMP알고리즘이다.

이해하는데 오래 걸린 알고리즘이다.

 

먼저 찾을 패턴을 통해 PI배열을 만든다.

 

AABA = [0,1,0,1]

ABAB = [0,0,1,2]

AABBAAB = [0,1,0,0,1,2,3]

 

이런 식으로 첫 문자의 패턴에서 중복되는 문자들을 기록해 둔다.

 

 

이 PI배열을 가지고 이제 문자열에서 패턴을 찾는다.

겹치는 부분이 있었다면 거기까지 건너뛰어 패턴을 찾기에 시간절약이 좋다.

 

class Solution:
    def countMatchingSubarrays(self, list_data, pattern):

        all_string = []
        answer = 0
        for i in range(len(list_data)-1):
            ttemp = list_data[i] - list_data[i+1]
            if ttemp > 0:
                all_string.append(-1)
            elif ttemp == 0:
                all_string.append(0)
            else:
                all_string.append(1)

        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
        i = 0
        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):
                    answer += 1
                    i = table[i-1]

        return answer