ให้สตริง s และ Queries Q[i]=(l,r) สำหรับ Substring s[l:r] หาจำนวน Substring ใน s ที่ "Similar" (โครงสร้างตัวอักษรซ้ำเหมือนกัน)
ตัวอย่าง: s="hjhhbcbk", Q=[(1,2),(2,4)] → [6,1]
ขั้นตอน (Fingerprint + Brute Force)
- สร้าง Fingerprint สำหรับทุก Substring ยาว 10 (Pattern ของตัวอักษร)
- ต่อ Query: ดึง Pattern ของ
s1 = s[l:r] - วนทุกตำแหน่งใน
sเช็คว่า Pattern ตรงกัน (Isomorphic)
ตัวอย่างโค้ด
fp = []
def calc_fingerprint(s):
d = {s[0]: 0}
fp_str = "0"
j = 1
for i in range(1, len(s)):
if s[i] not in d:
d[s[i]], j = j, j+1
fp_str += str(d[s[i]])
return int(fp_str)
def solve(s, Q):
if len(s) > 10:
for i in range(len(s)-10):
fp.append(calc_fingerprint(s[i:i+10]))
ret = []
for a, b in Q:
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
d = {}
s2 = s[i:i+(b-a)+1]
for i in range(b-a+1):
if s2[i] not in d:
if s1[i] in d.values():
break
d[s2[i]] = s1[i]
if d[s2[i]] != s1[i]:
break
else:
k += 1
ret.append(k)
return ret
s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q)) # Output: [6, 1]อินพุต
"hjhhbcbk", [(1,2), (2,4)]
เอาต์พุต
[6, 1]
