Z-ფუნქცია

Z-ფუნქცია სტრიქონის ყოველი პოზიციისთვის გვეუბნება, რა სიგრძეზე ემთხვევა ის ამავე სტრიქონის დასაწყისს. ერთი წრფივი გავლა გვაძლევს შაბლონის ძებნას, პერიოდებსა და საზღვრებს, და ბევრისთვის მისი დამახსოვრება KMP-ზე ადვილია.

მოწინავე⏱ 10 წთ

←ეყრდნობა

11პრეფიქს-ფუნქცია და KMPZ-ფუნქცია სტრიქონის დასაწყისთან დამთხვევას ზომავს, ისევე როგორც პრეფიქს-ფუნქცია საზღვრებს.1პრეფიქსული ჯამები, ორი მაჩვენებელი, მოცურავი ფანჯარაის უმარჯვენესი დამთხვევის [l, r] ფანჯარას ინახავს, რომ უკვე გაკეთებული შედარებები გამოტოვოს.

გზას უხსნის→

+მანაკერის ალგორითმიმანაკერი Z-ფუნქციის უმარჯვენეს ფანჯარას იყენებს, რომ ყოველი ცენტრი უკვე ცნობილი პასუხიდან დაიწყოს.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01რას ნიშნავს z[i]

z[i] არის მთელი სტრიქონის s-ისა და მისი სუფიქსის s[i..]-ის უგრძესი საერთო პრეფიქსის სიგრძე. სხვა სიტყვებით: ერთდროულად დავიწყოთ კითხვა i-დან და 0-დან და დავთვალოთ, რამდენი სიმბოლო ემთხვევა.

s = AABAAAB-სთვის z = [0, 1, 0, 2, 3, 1, 0]. მაგალითად z[4] = 3, რადგან s[4..6] = AAB ემთხვევა პირველ სამ სიმბოლოს AAB. შეთანხმებით z[0] = 0 (ზოგი n-ს წერს).

ყოველი z[i]-ის პირდაპირი შედარებით დათვლა უარეს შემთხვევაში O(n²)-ია, მაგალითად AAAA…A-ზე. ნამდვილი ალგორითმი შრომას ხელახლა იყენებს და O(n)-ს აღწევს.

02z-ბლოკი: გამოიყენე უკვე დამთხვეული

ვინახავთ z-ბლოკს [l, r): პრეფიქსთან დამთხვევას, რომელიც ყველაზე შორს აღწევს მარჯვნივ. მის შიგნით s[l..r) არის s[0..r−l)-ის ასლი. ამიტომ ბლოკში მყოფი i პოზიციის სარკე დასაწყისთან არის i − l, და z[i − l] უკვე ვიცით.

თუ i < r: ვიწყებთ z[i] = min(r − i, z[i − l])-დან. min არ გვაძლევს ბლოკის კიდის მიღმა არსებულის ნდობის უფლებას.
სხვა შემთხვევაში ვიწყებთ 0-დან.
შემდეგ პირდაპირი შედარებით ვაგრძელებთ და, თუ დამთხვევა r-ს გასცდა, ბლოკს [i, i + z[i])-ზე გადავწევთ.

ყოველი წარმატებული დამატებითი შედარება r-ს მარჯვნივ წევს, r კი მარცხნივ არასოდეს მიდის. ამიტომ სულ სამუშაო O(n)-ია, KMP-ის მსგავსი ამორტიზებული არგუმენტით.

03შაბლონის ძებნა P#T-ით

ტექსტ T-ში შაბლონ P-ს საპოვნელად ავაგოთ P + "#" + T, სადაც # არცერთ სტრიქონში არ გვხვდება, და დავთვალოთ მისი Z-ფუნქცია. სადაც z[i] = |P|, იქ შაბლონი T-ში i − |P| − 1 პოზიციაზე გვხვდება.

გამყოფი მნიშვნელოვანია: ის დამთხვევას P-ის ბოლოს იქით გაგრძელების საშუალებას არ აძლევს, ამიტომ z-ის არცერთი მნიშვნელობა |P|-ს ვერ გადააჭარბებს.

Z-ფუნქცია და პრეფიქს-ფუნქცია ერთსა და იმავე ინფორმაციას ატარებს და ერთმანეთში გარდაიქმნება. აირჩიე ის, რომელსაც უშეცდომოდ უფრო ადვილად დაწერ. Z პირდაპირ გვაძლევს სტრიქონის პერიოდებსაც: p პერიოდია, თუ z[p] = n − p.

ფასი ერთი შეხედვით

Z-ფუნქციაO(n)

შაბლონის ძებნა (P#T)O(n + m)

მეხსიერებაO(n + m)

დაიმახსოვრე

z[i] არის s-ისა და s[i..]-ის უგრძესი საერთო პრეფიქსის სიგრძე.
z-ბლოკში ვიწყებთ სარკული მნიშვნელობიდან min(r − i, z[i − l]); რადგან r მხოლოდ მარჯვნივ მოძრაობს, მთელი გავლა O(n)-ია.
გაუშვი Z სტრიქონზე P + "#" + T: ყოველი z[i] = |P| შაბლონის დამთხვევაა.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე მონიშნულ z-ბლოკს: როცა i მასში ხვდება, z[i] ნულიდან კი არა, გადმოწერილი მნიშვნელობიდან იწყება.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

Z-ფუნქცია

AABAAAB

z[]

	A	A	B	A	A	A	B
z	0	·	·	·	·	·	·

Z-ფუნქცია: z[i] = i-დან დაწყებული უგრძესი ქვესტრიქონის სიგრძე, რომელიც მთელი სტრიქონის პრეფიქსიცაა. ვინახავთ „z-ბლოკს“ [l,r], ანუ ყველაზე მარჯვნივ მიმავალ დამთხვევას.

ფსევდოკოდი

 1 z[0] = 0; maintain a z-box [l,r] = rightmost match with a prefix 2 if i < r: z[i] = min(r-i, z[i-l])     // mirror inside the box 3 else: z[i] = 0 4 extend z[i] by explicit comparisons; push [l,r] right if it grows

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

რა არის "ABAB"-ის Z-ფუნქცია (z[0] = 0)?

№2

z-ბლოკია [l, r) = [4, 9), z[1] = 6. რა არის z[5]-ის საწყისი მნიშვნელობა?

№3

რატომ ვსვამთ გამყოფს # P-სა და T-ს შორის?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

CSESString Matching დამწყები↗CSESFinding Borders საშუალო↗CSESString Functions საშუალო↗LeetCodeSum of Scores of Built Strings მოწინავე↗