Python에서 다른 쿼리에 대한 문자열의 다른 부분 문자열 수를 찾는 프로그램

길이가 n인 문자열 s가 있다고 가정합니다. 또한 Q[i]에는 (l, r) 쌍이 포함된 쿼리 Q 목록이 있습니다. 각 쿼리에 대해 l과 r 사이의 포함 범위에 있는 s의 다른 부분 문자열 수를 계산해야 합니다.

따라서 입력이 s ="ppqpp" Q =[(1,1),(1,4),(1,1),(0,2)]와 같으면 출력은 [1,8, 1,5] 때문에

• 쿼리(1, 1)의 경우 유일한 하위 문자열은 'p'이므로 출력은 1입니다.

• 쿼리(1, 4)의 경우 하위 문자열은 'p', 'q', 'pq', 'qp', 'pp', 'pqp', 'qpp' 및 'pqpp'이므로 출력은 8

• 다시 쿼리(1, 1)의 경우 유일한 하위 문자열은 'p'이므로 출력은 1입니다.

• 쿼리(0, 2)의 경우 부분 문자열은 'p', 'q', 'pp', 'pq', 'ppq'이므로 출력은 8입니다.

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

• kasai() 함수를 정의합니다. s, suff, n
이 걸립니다.
• lcp :=크기가 n이고 0으로 채워진 배열
• inv :=크기가 n이고 0으로 채워지는 배열
• 0 ~ n - 1 범위의 i에 대해
  • inv[suff [i]] :=나
• k :=0
• 0 ~ n - 1 범위의 i에 대해
  • inv [i]가 n-1과 같으면
    • k :=0
    • 다음 반복으로 이동
  • j :=suff[inv [i] + 1]
  • i + k
  • k :=k + 1
• lcp[inv [i]] :=k
• k> 0이면
  • k :=k - 1

예

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

def kasai (s, suff, n):
   lcp = [0] * n
   inv = [0] * n
   for i in range (n):
      inv [suff [i]] = i
   k = 0
   for i in range (n):
      if inv [i] == n-1:
         k = 0
         continue
      j = suff [inv [i] + 1]
      while i + k <n and j + k <n and s [i + k] == s [j + k]:
         k += 1
      lcp [inv [i]] = k
      if k> 0:
         k -= 1
   return lcp

def solve(s, Q):
   res = []
   for i in range (len(Q)):
      left, right = Q[i]
      sub = s [left: right + 1]
      length = right-left + 1

      suffix = [[i, sub [i:]] for i in range (length)]

      suffix.sort (key = lambda x: x [1])
      suff, suffix = [list (t) for t in zip (* suffix)]

      lcp = kasai (sub, suff, length)
      count = len (suffix [0])
      for i in range (length-1):
         count += len (suffix [i + 1]) - lcp [i]

      res.append(count)
   return res

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

입력

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

출력

[1, 8, 1, 5]