გულუბრყვილო შაბლონის ძებნა

Ctrl+F, grep, str.find: ტექსტში შაბლონის პოვნა პროგრამების ერთ-ერთი ყველაზე ხშირი საქმეა. დავიწყოთ უბრალო მეთოდით, რომ ზუსტად დავინახოთ, სად კარგავს დროს.

დამწყები⏱ 8 წთ

←ეყრდნობა

0სირთულე და ზრდის ტემპიშედარებების დათვლა O(n·m)-ს იძლევა და აჩვენებს, სად იკარგება შრომა.1პრეფიქსული ჯამები, ორი მაჩვენებელი, მოცურავი ფანჯარაგულუბრყვილო ძებნა m სიგრძის ფანჯარას ტექსტზე აცურებს.

გზას უხსნის→

11მოძრავი ჰეში და რაბინ-კარპირაბინ-კარპი იგივე ფანჯარას აცურებს, ოღონდ სიმბოლოებამდე ანაბეჭდებს ადარებს.11პრეფიქს-ფუნქცია და KMPKMP გულუბრყვილო ძებნას ტექსტში უკან დაბრუნების ჩვევას აშორებს.+მანაკერის ალგორითმიის ყოველი ცენტრიდან გაფართოებით, გულუბრყვილო O(n²) იდეით იწყება და ზედმეტ შრომას აშორებს.

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

ისწავლე

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

01მოვსინჯოთ ყოველი ძვრა

გვაქვს n სიგრძის ტექსტი T და m სიგრძის შაბლონი P. გულუბრყვილო ალგორითმი P-ს T-ის ქვეშ ძვრაზე s = 0 დებს, სიმბოლოებს მარცხნიდან მარჯვნივ ადარებს და პირველივე შეუსაბამობაზე ჩერდება. შემდეგ შაბლონს ერთი პოზიციით მარჯვნივ წევს და ისევ მისი პირველი სიმბოლოდან იწყებს.

თუ m-ვე სიმბოლო დაემთხვა, s დამთხვევის პოზიციაა. ბოლო აზრიანი ძვრაა n − m: მის შემდეგ შაბლონი ტექსტის ბოლოს გადასცდებოდა.

კოდში ეს ორი ჩადგმული ციკლია, დაახლოებით ხუთი სტრიქონი. სწორედ ესაა მისი ძალა: მარტივად იწერება, ძნელია შეცდომის დაშვება და ხშირად საკმარისად სწრაფიცაა.

ყოველი სტრიქონი ერთი ძვრაა. მწვანე = დაემთხვა, წითელი = პირველი შეუსაბამობა, ნაცრისფერი = არ შედარებულა.

02უარესი შემთხვევა: n·m

ჩვეულებრივ ტექსტზე ძვრების უმეტესობა პირველსა ან მეორე სიმბოლოზე წყდება, ამიტომ გულუბრყვილო მეთოდი დაახლოებით O(n)-ში მუშაობს. პრობლემა ისეთი შემავალი მონაცემებია, სადაც ყოველ ძვრაზე თითქმის მთელი შაბლონი ემთხვევა.

ავიღოთ T = AAAAAAAAAA და P = AAAB. n − m + 1 ძვრიდან თითოეულზე სამი A ემთხვევა და მხოლოდ B ვერ. ესაა m შედარება ყოველ ძვრაზე, სულ (n − m + 1)·m, ანუ O(n·m).

n = 10⁶ და m = 10³ შემთხვევაში ეს დაახლოებით მილიარდი შედარებაა. განმეორებადი მონაცემები (დნმ, ლოგები, გენერირებული ტესტები) ამ შემთხვევას რეალურად აწყდება.

03სად იკარგება შრომა

ნახე, რა ხდება შეუსაბამობის შემდეგ შაბლონის j პოზიციაზე. ახლახან გავიგეთ, რომ T[s..s+j−1] უდრის P[0..j−1]-ს: ეს j სიმბოლო ტექსტიდან უკვე ვიცით. გულუბრყვილო მეთოდი ყველაფერს ივიწყებს, ერთი ნაბიჯით იწევს და მათ უმეტესობას ხელახლა კითხულობს.

ამ ეტაპის ორი ჭკვიანი ალგორითმი ამას სხვადასხვაგვარად ასწორებს:

მოძრავი ჰეში მთელ ფანჯარას ერთი რიცხვის შედარებით ამოწმებს.
KMP უკვე დამთხვეულ ნაწილს იყენებს, რომ გადაწყვიტოს, რამდენით შეუძლია უსაფრთხოდ გადახტომა, ამიტომ ტექსტში უკან არასოდეს ბრუნდება.

მაინც, მოკლე შაბლონებისთვის გულუბრყვილო ძებნა კარგი ნაგულისხმევი არჩევანია და ის საზომია, რომლითაც სწრაფ კოდს ამოწმებ.

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

ჩვეულებრივი ტექსტი≈ O(n)

უარესი შემთხვევაO(n·m)

დამატებითი მეხსიერებაO(1)

დაიმახსოვრე

გულუბრყვილო ალგორითმი ყოველ ძვრას სინჯავს და მარცხნიდან მარჯვნივ ადარებს პირველ შეუსაბამობამდე.
მისი უარესი შემთხვევა O(n·m)-ია და მიიღწევა განმეორებად მონაცემებზე, მაგ. AAAA…A და შაბლონი AA…AB.
ფლანგვა უკვე დამთხვეული სიმბოლოების ხელახალი კითხვაა; ჰეშირება და KMP მას აქრობს.

ითამაშე

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

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

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

გულუბრყვილო ძებნა · შედარებები: 0

AABAACAADAABAABA

AABA············

ვეძებთ შაბლონს "AABA" (სიგრძე 4) 16 სიგრძის ტექსტში ყოველი ძვრის მოსინჯვით.

ფსევდოკოდი

 1 for each shift s in text: 2   match pattern char by char 3   on the first mismatch, abandon this shift 4   if all chars matched → occurrence at s 5 // worst case O(n·m)

1 / 1

შეამოწმე

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

№1

ტექსტის სიგრძე n = 12, შაბლონის m = 4. რამდენ ძვრას სინჯავს გულუბრყვილო ალგორითმი?

№2

რომელ შემავალ მონაცემზეა გულუბრყვილო ალგორითმი ყველაზე ნელი?

№3

ძვრაზე s პირველი შეუსაბამობა შაბლონის j = 3 პოზიციაზეა. რა ვიცით ზუსტად?

ივარჯიშე

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

LeetCodeFind the Index of the First Occurrence in a String დამწყები↗LeetCodeRotate String დამწყები↗LeetCodeRepeated Substring Pattern დამწყები↗CSESString Matching საშუალო↗