Python에서 각 쿼리에 대해 유사한 하위 문자열의 수를 계산하는 프로그램

두 개의 문자열 s와 쿼리 Q 세트가 있다고 가정합니다. Q[i]에 쌍 (l, r)이 포함되어 있는 경우 l에서 r까지 s의 각 부분 문자열에 대해 x에서 y까지의 부분 문자열 s의 수를 찾아야 합니다. 비슷하다. 두 문자열 s와 t는 다음 규칙을 따르면 비슷합니다. -

• 길이가 같습니다.

• 각 인덱스 쌍(i, j)에 대해 s[i]가 s[j]와 같으면 t[i] =t[j]를 충족해야 하고 s[i]가 s와 같지 않으면 유사하게 [j], t[i]와 t[j]는 달라야 합니다.

따라서 입력이 s ="hjhhbcbk" Q =[(1,2), (2,4)]와 같으면 출력은 [6, 1]이 됩니다.

• 첫 번째 쿼리의 경우 유사한 하위 문자열은 "hj", "jh", "hb", "bc", "cb" 및 "bk"입니다.
• 첫 번째 쿼리의 경우 유사한 하위 문자열은 "jhh"입니다.

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

• fp :=새 목록
• calc_fingerprint() 함수를 정의합니다. 시간이 걸립니다
• dict :=새 사전, 초기에 키-값 쌍(s[0], 0) 삽입
• fp :="0"
• j :=1
• 범위 1에서 s - 1 크기의 i에 대해
  • s[i]가 dict에 없으면
    • dict[s[i]] :=j
    • j =j+1
  • fp :=fp + dict[s[i]]의 문자열 표현
• fp의 정수 형식 반환
• 메인 방법에서 다음을 수행하십시오. -
• 크기가 s> 10이면
  • 0에서 s - 10 사이의 범위에 있는 i에 대해
    • x :=calc_fingerprint(s[인덱스 i에서 i+9까지])
    • fp 끝에 x 삽입
• ret :=새 목록
• 0에서 Q - 1의 크기 범위에 있는 i에 대해
  • (a, b) :=Q[i]
  • s1 :=인덱스 a-1에서 b-1까지 s의 부분 문자열
  • k :=0
  • 0 ~ s - (b-a) 범위의 i에 대해
    • b-a> 9이고 fp[a-1]이 fp[i]와 같지 않으면
      • 다음 반복으로 이동
    • dict :=새로운 빈 지도
    • s2 :=인덱스 i에서 i+(b-a)까지 s의 부분 문자열
    • 0에서 b-a 범위의 i에 대해
      • s2[i]가 사전에 없으면
        • s1[i]가 dict의 값에 있으면
          • 루프에서 나오다
        • 딕셔너리[s2[i]] :=s1[i]
      • dict[s2[i]]가 s1[i]와 같지 않으면
        • 루프에서 나오다
    • 그렇지 않으면
      • k :=k + 1
  • ret 끝에 k 삽입
• 반환

예시

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

fp = []

def calc_fingerprint(s):
   dict = {s[0]: 0}
   fp = "0"
   j = 1
   for i in range(1, len(s)):
      if s[i] not in dict:
         dict[s[i]], j = j, j+1
      fp += str(dict[s[i]])
   return int(fp)

def solve(s, Q):
   if len(s) > 10:
      for i in range(0, len(s)-10):
         fp.append(calc_fingerprint(s[i: i+10]))

   ret = []
   for i in range(len(Q)):
      a, b = Q[i]
      s1 = s[a-1:b]
      k = 0
      for i in range(len(s)-(b-a)):
         if b-a > 9 and fp[a-1] != fp[i]:
            continue
         dict = {}
         s2 = s[i:i+(b-a)+1]
         for i in range(b-a+1):
            if s2[i] not in dict:
               if s1[i] in dict.values(): break
               dict[s2[i]] = s1[i]
            if dict[s2[i]] != s1[i]: break
         else:
            k += 1
      ret.append(k)

   return ret

s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q))

입력

"hjhhbcbk", [(1,2), (2,4)]

출력

[6, 1]