Algo Visualizedდაიწყე სწავლა

პრეფიქს-ფუნქცია და KMP

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

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

←ეყრდნობა

11გულუბრყვილო შაბლონის ძებნაKMP გულუბრყვილო ძებნას ტექსტში უკან დაბრუნების ჩვევას აშორებს.10ერთგანზომილებიანი დპ: მონეტები და LISპრეფიქს-ფუნქცია მარცხნიდან მარჯვნივ ივსება, ყოველი მნიშვნელობა წინაებიდან იგება.5ტრაი და ავტოშევსებაპრეფიქს-ფუნქცია შაბლონის ტრაიში დაბრუნების ბმულებივით მუშაობს: შეუსაბამობისას გადადი უგრძეს საზღვარზე.

გზას უხსნის→

+Z-ფუნქციაZ-ფუნქცია სტრიქონის დასაწყისთან დამთხვევას ზომავს, ისევე როგორც პრეფიქს-ფუნქცია საზღვრებს.
1ისწავლე2ითამაშე3შეამოწმე4ივარჯიშე
01

ისწავლე

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

01საზღვრები და პრეფიქს-ფუნქცია

სტრიქონის საზღვარი ისეთი საკუთარი პრეფიქსია, რომელიც სუფიქსიცაა. ABAB-ში AB ისიცაა, რითაც იწყება, და ისიც, რითაც მთავრდება.

პრეფიქს-ფუნქცია შაბლონის ყოველი i პოზიციისთვის ინახავს P[0..i]-ის უგრძესი საზღვრის სიგრძეს:

π[i] = P[0..i]-ის უგრძესი საკუთარი პრეფიქსი, რომელიც მისი სუფიქსიცაა

ABABC-სთვის π = [0, 0, 1, 2, 0]. რისთვის გვჭირდება? თუ ABAB დაემთხვა და შემდეგ ჩავვარდით, ბოლო ორი წაკითხული სიმბოლო (AB) უკვე შაბლონის პირველი ორი სიმბოლოა. მათი შენახვა შეგვიძლია, თავიდან დაწყების ნაცვლად. სწორედ ეს მარტივი დაკვირვება ამოძრავებს მთელ ალგორითმს.

პრეფიქსისუფიქსიA0B1A2B3C4π00120pat[0..3] = ABAB: საზღვარი „AB“, ამიტომ π[3] = 2

02KMP-ის სკანირება

KMP ტექსტს i მაჩვენებლით გაუყვება და ინახავს j-ს, შაბლონის ამჟამად დამთხვეული სიმბოლოების რაოდენობას.

  • თუ T[i] = P[j]: j გავზარდოთ, i წავწიოთ.
  • თუ განსხვავდება და j > 0: j = π[j−1] და T[i] ისევ შევადაროთ. ეს შაბლონს მარჯვნივ წევს და დამთხვეულ საზღვარს ინახავს.
  • თუ განსხვავდება და j = 0: უბრალოდ წავწიოთ i.
  • თუ j = m: დამთხვევა i − m + 1 პოზიციაზე, შემდეგ j = π[m−1], რომ გადაფარული დამთხვევებიც ვიპოვოთ.

ტექსტის მაჩვენებელი i უკან არასოდეს მიდის. სწორედ ეს თვისება ხდის KMP-ს სწრაფს.

შეუსაბამობა: A ≠ C, j = 4ABABABCABABCABABCj = π[3] = 2: AB უკვე დამთხვეულიაABABABCABABCABABCi არ იძვრისshift = j − π[j−1] = 4 − 2 = 2
შაბლონი ორი პოზიციით ხტება, ტექსტის მაჩვენებელი კი იმავე სიმბოლოზე რჩება.

03π-ის აგება იმავე იდეით

π-ს იგივე ლოგიკით ვითვლით, ოღონდ შაბლონს თავის თავს ვადარებთ. ვინახავთ k = π[i−1]-ს, მიმდინარე საზღვრის სიგრძეს. i პოზიციამდე გასაგრძელებლად P[i]-ს P[k]-ს ვადარებთ:

  • ტოლია: π[i] = k + 1
  • განსხვავდება და k > 0: გადავიდეთ შემდეგ, უფრო მოკლე საზღვარზე, k = π[k−1], და ვცადოთ ისევ
  • განსხვავდება და k = 0: π[i] = 0

ეს დინამიური პროგრამირებაა შაბლონზე: ყოველი მნიშვნელობა წინებს იყენებს. აგება O(m) ღირს, სკანირება O(n), რადგან j მაქსიმუმ იმდენჯერ შემცირდება, რამდენჯერაც გაიზარდა. ერთად უარეს შემთხვევაშიც O(n + m).

n = 1000, m = 100, ტექსტი AAAA…, შაბლონი AA…ABგულუბრყვილო≈ 90 100KMP≤ 2 000 შედარება(n − m + 1)·m vs ≤ 2n

04როდის გამოვიყენოთ KMP

ჩვეულებრივ ტექსტში ერთჯერადი ძებნისთვის ენის ჩაშენებული find საკმარისია. KMP-ს მიმართე, როცა:

  • გჭირდება გარანტირებული O(n + m), მაგალითად ოლიმპიადის მტრულ ტესტებზე
  • ტექსტი ნაკადად შემოდის და უკან დაბრუნება შეუძლებელია
  • კითხვა თავად შაბლონზეა: მისი უმოკლესი პერიოდია m − π[m−1], საზღვრები კი π[m−1], π[π[m−1]−1], …

გავრცელებული ხერხი: პრეფიქს-ფუნქცია გაუშვი P + "#" + T-ზე, სადაც # არცერთ სტრიქონში არ გვხვდება. ყოველი პოზიცია, სადაც π = m, დამთხვევას აღნიშნავს. ასე ძებნისთვის ცალკე სკანირების კოდიც აღარ გვჭირდება, საკმარისია მხოლოდ π-ის აგება.

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

π-ის აგებაO(m)
ტექსტის სკანირებაO(n)
სულ, უარეს შემთხვევაშიO(n + m)
მეხსიერებაO(m)

დაიმახსოვრე

  1. π[i] შაბლონის i-ზე დამთავრებული პრეფიქსის უგრძესი საზღვრის (პრეფიქსი = სუფიქსი) სიგრძეა.
  2. შეუსაბამობისას KMP ანიჭებს j = π[j−1]-ს და ტექსტის მაჩვენებელს ადგილზე ტოვებს, ანუ i უკან არასოდეს მიდის.
  3. KMP უარეს შემთხვევაშიც O(n + m)-ია, π კი სტრიქონის საზღვრებსა და პერიოდებსაც გვაძლევს.
02

ითამაშე

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

👀 რას უყურო: ჯერ π აიგება. შემდეგ, სკანირებისას, უყურე მონიშნულ სიმბოლოს ტექსტში: ის მხოლოდ მარჯვნივ მიდის, შაბლონი კი ხტება.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →
✎ შენი მონაცემებიტექსტი 16 სიმბოლომდე, შაბლონი 6-მდე. განმეორებადი შაბლონები (ABAB, AAB) π-ს საინტერესოს ხდის.

პრეფიქს-ფუნქცია და KMP

ABABC

შაბლონი "ABABC" · π

ABABC
π0····
KMP ჯერ π-ს აგებს, სადაც π[i] = pat[0..i]-ის უგრძესი საკუთარი პრეფიქსის სიგრძე, რომელიც სუფიქსიცაა. ეს დპ-ია შაბლონზე.

ფსევდოკოდი

 1 π[0] = 0 2   while k>0 and pat[i]≠pat[k]: k = π[k-1]   // fall back 3   if pat[i]==pat[k]: k++;  π[i] = k 4 scan: j = matched length so far 5   on mismatch with j>0: j = π[j-1]   (keep the border, no reread) 6   on match: advance both; i never moves backward 7   when j == m: report occurrence
1 / 1
03

შეამოწმე

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

№1

რა არის "AABAA"-ს პრეფიქს-ფუნქცია?

№2

შაბლონი ABABC (π = 0,0,1,2,0). დაემთხვა ABAB (j = 4), ტექსტის შემდეგი სიმბოლოა A. რა იქნება ახალი j?

№3

რატომ არის KMP-ის სკანირება O(n), თუმცა შიგნით while ციკლია?

04

ივარჯიშე

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

LeetCodeFind the Index of the First Occurrence in a String დამწყები↗CSESFinding Borders საშუალო↗CSESFinding Periods საშუალო↗LeetCodeLongest Happy Prefix მოწინავე↗LeetCodeShortest Palindrome მოწინავე↗