Giả sử chúng ta có một chuỗi s có độ dài là n. Chúng ta cũng có một danh sách các truy vấn Q, trong đó Q [i] chứa một cặp (l, r). Đối với mỗi truy vấn, chúng ta phải đếm số chuỗi con khác nhau của s trong phạm vi bao gồm từ l đến r.
Vì vậy, nếu đầu vào là s ="ppqpp" Q =[(1,1), (1,4), (1,1), (0,2)], thì đầu ra sẽ là [1,8, 1,5] bởi vì
-
Đối với truy vấn (1, 1) chuỗi con duy nhất là 'p' vì vậy đầu ra là 1
-
Đối với truy vấn (1, 4) các chuỗi con là 'p', 'q', 'pq', 'qp', 'pp', 'pqp', 'qpp' và 'pqpp', vì vậy đầu ra là 8
-
Một lần nữa đối với truy vấn (1, 1) chuỗi con duy nhất là 'p' vì vậy đầu ra là 1
-
Đối với truy vấn (0, 2) các chuỗi con là 'p', 'q', 'pp', 'pq', 'ppq', vì vậy đầu ra là 8.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Định nghĩa một hàm kasai (). Điều này sẽ nhận s, đủ, n
- lcp:=một mảng có kích thước n và điền bằng 0
- inv:=một mảng có kích thước n và điền bằng 0
- đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
- inv [đủ [i]]:=i
- k:=0
- đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
- nếu inv [i] giống n-1 thì
- k:=0
- chuyển sang lần lặp tiếp theo
- j:=Suff [inv [i] + 1]
- trong khi i + k
- k:=k + 1
- nếu inv [i] giống n-1 thì
- lcp [inv [i]]:=k
- nếu k> 0, thì
- k:=k - 1
- (trái, phải):=Q [i]
- sub:=chuỗi con của s từ chỉ mục từ trái sang phải
- length:=right-left + 1
- hậu tố:=danh sách các cặp (i, chuỗi con của chỉ số con từ chỉ số i đến cuối) cho mỗi thứ i trong phạm vi từ 0 đến độ dài - 1
- sắp xếp hậu tố dựa trên mục thứ hai của cặp chuỗi con
- lcp:=kasai (phụ, đủ, dài)
- count:=kích thước của hậu tố [0]
- đối với tôi trong phạm vi 0 đến length-2, hãy thực hiện
- count:=count + kích thước của hậu tố [i + 1] - lcp [i]
- chèn số lượng vào cuối res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
"pptpp", [(1,1),(1,4),(1,1),(0,2)]
Đầu ra
[1, 8, 1, 5]