สมมติว่าเรามีสตริง s เราต้องหาจำนวนสตริงย่อยที่เป็นเนื้อเดียวกันของ s คำตอบอาจมีขนาดใหญ่มาก ดังนั้นให้ส่งคืนโมดูโลคำตอบ 10^9+7 กล่าวกันว่าสตริงเป็นเนื้อเดียวกันเมื่ออักขระทั้งหมดของสตริงเหมือนกัน
ดังนั้น หากอินพุตเป็น s ="xyyzzzzxx" ผลลัพธ์จะเป็น 13 เนื่องจากสตริงย่อยที่เป็นเนื้อเดียวกันมีการระบุไว้เช่น
-
1."x" ปรากฏขึ้นสามครั้ง
-
"xx" ปรากฏขึ้นหนึ่งครั้ง
-
3. "y" ปรากฏขึ้นสองครั้ง
-
"ปปปป" ปรากฏขึ้นหนึ่งครั้ง
-
5. "z" ปรากฏขึ้นสามครั้ง
-
"zz" ปรากฏขึ้นสองครั้ง
-
"zzz" ปรากฏขึ้นหนึ่งครั้ง
ดังนั้น (3 + 1 + 2 + 1 + 3 + 2 + 1) =13
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
s :=s ต่อ "@"
-
h:=แผนที่ใหม่
-
ก่อนหน้า:=s[0]
-
ค:=1
-
สำหรับแต่ละ i ใน s จากดัชนี 1 ถึงจุดสิ้นสุด ทำ
-
ถ้าก่อนหน้าไม่เหมือนกับ i แล้ว
-
ถ้า prev*c มีอยู่ใน h แล้ว
-
h[prev*c] :=h[prev*c] + 1
-
-
มิฉะนั้น
-
h[prev*c]:=1
-
-
ค:=1
-
-
ถ้าก่อนหน้าเหมือนกับ i แล้ว
-
ค :=ค + 1
-
-
ก่อนหน้า :=ฉัน
-
-
fin:=0
-
สำหรับแต่ละ i ใน h ทำ
-
t:=ขนาดของ i
-
k:=0
-
ในขณะที่ t ไม่เหมือนกับ 0 ทำ
-
k :=k + t
-
t :=t - 1
-
-
fin :=fin + k*h[i]
-
-
กลับ fin mod 10^9+7
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
"xyyzzzxx"
ผลลัพธ์
13
