Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số chuỗi con đồng nhất của s. Câu trả lời có thể rất lớn, vì vậy hãy trả về câu trả lời modulo 10 ^ 9 + 7. Một chuỗi được cho là đồng nhất khi tất cả các ký tự của chuỗi đều giống nhau.
Vì vậy, nếu đầu vào là s ="xyyzzzxx", thì đầu ra sẽ là 13 vì các chuỗi con đồng nhất được liệt kê giống như
-
1. "x" xuất hiện ba lần.
-
"xx" xuất hiện một lần.
-
3. "y" xuất hiện hai lần.
-
"yy" xuất hiện một lần.
-
5. "z" xuất hiện ba lần.
-
"zz" xuất hiện hai lần.
-
"zzz" xuất hiện một lần.
vì vậy, (3 + 1 + 2 + 1 + 3 + 2 + 1) =13.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
s:=s nối "@"
-
h:=một bản đồ mới
-
trước:=s [0]
-
c:=1
-
đối với mỗi i trong s từ chỉ mục 1 đến cuối, hãy thực hiện
-
nếu trước không giống với tôi, thì
-
nếu trước * c có trong h, thì
-
h [trước * c]:=h [trước * c] + 1
-
-
nếu không,
-
h [trước * c]:=1
-
-
c:=1
-
-
nếu trước đây giống với tôi, thì
-
c:=c + 1
-
-
trước:=i
-
-
vây:=0
-
cho mỗi tôi trong h, làm
-
t:=kích thước của tôi
-
k:=0
-
trong khi t không giống 0, làm
-
k:=k + t
-
t:=t - 1
-
-
fin:=fin + k * h [i]
-
-
trả về bản mod vây 10 ^ 9 + 7
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(s):
s+="@"
h={}
prev=s[0]
c=1
for i in s[1:]:
if prev!=i:
if prev*c in h:
h[prev*c]+=1
else:
h[prev*c]=1
c=1
if prev == i:
c += 1
prev = i
fin=0
for i in h:
t=len(i)
k=0
while t!=0:
k+=t
t-=1
fin+=k*h[i]
return fin % 1000000007
s = "xyyzzzxx"
print(solve(s)) Đầu vào
"xyyzzzxx"
Đầu ra
13