Python에서 다른 문자열의 모든 문자를 포함하는 문자열에서 가장 작은 창 찾기

2개의 문자열 s1과 s2가 있다고 가정하면 s2의 모든 문자가 효율적으로 사용되도록 s1에서 가장 작은 부분 문자열을 찾아야 합니다.

따라서 입력이 s1 ="나는 학생입니다", s2 ="mdn"과 같으면 출력은 "m a studen"이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• N :=26

• str_len :=main_str의 크기, patt_len :=패턴의 크기

• str_len

  • 반환 없음

• hash_pat :=크기가 N이고 0으로 채워지는 배열

• hash_str :=크기가 N이고 0으로 채워지는 배열

• 범위 0에서 patt_len까지의 i에 대해 수행

  • hash_pat[ASCII of(pattern[i]) ] :=hash_pat[ASCII of(pattern[i]) ] + 1

• 시작 :=0, 시작 인덱스 :=-1, min_len :=inf

• 개수 :=0

• 범위 0에서 str_len까지의 j에 대해 수행

  • hash_str[ASCII of(main_str[j]) ] :=hash_str[ASCII of(main_str[j]) ] + 1

  • hash_pat[ASCII of(main_str[j]) ]가 0과 같지 않고 hash_str[ASCII of(main_str[j]) ] <=hash_pat[ASCII of(main_str[j]) ]이면

    • 개수 :=개수 + 1

  • count가 patt_len과 같으면

    • hash_str[ASCII of(main_str[start]) ]> hash_pat[ASCII of(main_str[start]) ] 또는 hash_pat[ASCII of(main_str[start]) ]가 0과 같을 때 do

      • hash_str[ASCII of(main_str[start])]> hash_pat[ASCII of(main_str[start])]이면

        • hash_str[ASCII of(main_str[start]) ] :=hash_str[ASCII of(main_str[start]) ] - 1

      • 시작 :=시작 + 1

    • len_window :=j - 시작 + 1

    • min_len> len_window이면

      • min_len :=len_window

      • start_index :=시작

• start_index가 -1과 같으면

  • 반환 없음

• main_str의 하위 문자열 반환[인덱스 start_index에서 start_index + min_len까지]

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

N = 256
def get_pattern(main_str, pattern):
   str_len = len(main_str)
   patt_len = len(pattern)
   if str_len < patt_len:
      return None
   hash_pat = [0] * N
   hash_str = [0] * N
   for i in range(0, patt_len):
      hash_pat[ord(pattern[i])] += 1
   start, start_index, min_len = 0, -1, float('inf')
   count = 0
   for j in range(0, str_len):
      hash_str[ord(main_str[j])] += 1

      if (hash_pat[ord(main_str[j])] != 0 and hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]):
         count += 1
      if count == patt_len:
         while (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])] or hash_pat[ord(main_str[start])] == 0):
      if (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]):
         hash_str[ord(main_str[start])] -= 1
         start += 1
      len_window = j - start + 1
      if min_len > len_window:
         min_len = len_window
         start_index = start
   if start_index == -1:
      return None
   return main_str[start_index : start_index + min_len]
main_str = "I am a student"
pattern = "mdn"
print(get_pattern(main_str, pattern))

입력

"I am a student", "mdn"

출력

m a studen