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

მანაკერის ალგორითმი

„უგრძესი პალინდრომული ქვესტრიქონი“ კლასიკური გასაუბრების კითხვაა მარტივი O(n²) პასუხით. მანაკერის ალგორითმი ყველა პალინდრომს O(n)-ში პოულობს, Z-ფუნქციის მსგავსი სარკის ხერხით.

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

←ეყრდნობა

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

გზას უხსნის→

აქ გზამკვლევი სრულდება. გადახედე, რა გზა გაიარე.

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

ისწავლე

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

01პალინდრომი ცენტრიდან იზრდება

ყოველ კენტი სიგრძის პალინდრომს ცენტრალური სიმბოლო აქვს. განვსაზღვროთ d1[i], როგორც i-ზე ცენტრირებული უგრძესი კენტი პალინდრომის რადიუსი: ის ფარავს s[i − d1[i] + 1 .. i + d1[i] − 1]-ს და მისი სიგრძეა 2·d1[i] − 1.

abacaba-სთვის d1 = [1, 2, 1, 4, 1, 2, 1]. ცენტრ c-ს რადიუსი 4 აქვს: ეს მთელი სტრიქონია.

მარტივი მეთოდი ყოველი ცენტრიდან ფართოვდება, სანამ ორი გარე სიმბოლო ტოლია. ეს ადვილია და ხშირად საკმარისი, მაგრამ aaaa…a-ზე ყოველი ცენტრი შორს ფართოვდება და O(n²) გამოდის. შენიშნე ისიც, რომ r რადიუსის პალინდრომი იმავე ცენტრის გარშემო r − 1, r − 2, … რადიუსის პალინდრომებსაც შეიცავს, ამიტომ d1[i] i-ზე ცენტრირებულ პალინდრომებსაც ითვლის.

a0b1a2c3a4b5a6d11214121ცენტრი 3, რადიუსი 4 → „abacaba“, სიგრძე 2·4 − 1 = 7

02სარკე [l, r]-ის შიგნით

ვინახავთ [l, r]-ს, ჯერჯერობით ნაპოვნ პალინდრომს, რომელიც ყველაზე შორს აღწევს მარჯვნივ. პალინდრომი ორივე მიმართულებით ერთნაირად იკითხება, ამიტომ რაც მის შიგნით i პოზიციის გარშემო ხდება, იგივე მოხდა მისი სარკის, j = l + r − i-ის გარშემოც.

  • თუ i ≤ r: ვიწყებთ k = min(d1[j], r − i + 1)-დან. შეზღუდვა საჭიროა, რადგან r-ის მიღმა სარკე არაფერს გვეუბნება.
  • სხვა შემთხვევაში ვიწყებთ k = 1-დან.
  • შემდეგ ვაფართოებთ, სანამ s[i − k] = s[i + k], და თუ პალინდრომი ახლა r-ს სცდება, [l, r]-ს ვანახლებთ.

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

ყველაზე მარჯვენა პალინდრომი [l, r] = [0, 6]a0b1a2c3a4b5a6სარკე: l + r − i = 0 + 6 − 5 = 1d1[5] იწყება d1[1] = 2-დან

03ლუწი პალინდრომები და გამოყენება

ლუწი სიგრძის პალინდრომებს, მაგალითად abba-ს, ცენტრი ორ სიმბოლოს შორის აქვთ. შეგიძლია იმავე იდეით მეორე მასივი d2 დათვალო, ან უფრო მარტივი ხერხი გამოიყენო: ყველა სიმბოლოს შორის გამყოფი ჩასვა, #a#b#b#a#. ახლა ახალ სტრიქონში ყოველი პალინდრომი კენტი სიგრძისაა, ამიტომ d1-ის ერთი გაშვება ორივე სახეს ფარავს. საწყის სტრიქონში სიგრძეების მისაღებად რადიუსები ორზე გაყავი.

ტიპური გამოყენება:

  • უგრძესი პალინდრომული ქვესტრიქონი
  • ყველა პალინდრომული ქვესტრიქონის დათვლა: რადიუსების ჯამი
  • O(n) წინასწარი დამუშავების შემდეგ O(1)-ში შემოწმება, არის თუ არა ნებისმიერი s[l..r] პალინდრომი
„abba“-ს ცენტრი ორ ასოს შორისააabba# ჩავსვათ, და ცენტრი ერთი უჯრა გახდება#a#b#b#a#

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

გაფართოება ყოველი ცენტრიდანO(n²)
მანაკერიO(n)
მეხსიერებაO(n)

დაიმახსოვრე

  1. d1[i] არის i-ზე ცენტრირებული უგრძესი კენტი პალინდრომის რადიუსი; მისი სიგრძეა 2·d1[i] − 1.
  2. ყველაზე მარჯვენა პალინდრომში [l, r] ვიწყებთ სარკის რადიუსიდან, კიდით შეზღუდულით; r მხოლოდ მარჯვნივ მიდის, ამიტომ გავლა O(n)-ია.
  3. სიმბოლოებს შორის #-ის ჩასმა ლუწ პალინდრომებს კენტად აქცევს, ამიტომ ერთი მასივი ორივეს ფარავს.
02

ითამაშე

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

👀 რას უყურო: დააკვირდი „სარკის“ ნაბიჯებს: რადიუსი გადმოწერილი მნიშვნელობიდან იწყება და მხოლოდ საზღვრის მიღმა ნაწილი მოწმდება.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →
✎ შენი მონაცემები12 სიმბოლომდე, მაგ. სიტყვა შიგ პალინდრომით: xabacabay.

მანაკერის ალგორითმი

abacaba

d1 (რადიუსი)

abacaba
d1·······
მანაკერი ყველა პალინდრომს O(n)-ში პოულობს. d1[i] = i-ზე ცენტრირებული უგრძესი კენტი პალინდრომის რადიუსი. ვინახავთ ყველაზე მარჯვენა ცნობილ პალინდრომს [l,r].

ფსევდოკოდი

 1 d1[i] = radius of the longest odd palindrome centered at i 2 maintain the rightmost palindrome [l,r] 3 if i ≤ r: start k = min(r-i+1, d1[mirror])   // reuse the mirror 4 expand k by explicit comparisons; push [l,r] right if it grows
1 / 1
03

შეამოწმე

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

№1

რა არის d1 სტრიქონისთვის "aaa"?

№2

ყველაზე მარჯვენა პალინდრომია [l, r] = [2, 10], i = 8 და d1[4] = 5. რა არის საწყისი რადიუსი k, როცა i = 8?

№3

რატომ არის მანაკერი O(n) და არა O(n²)?

04

ივარჯიშე

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

LeetCodeLongest Palindromic Substring საშუალო↗LeetCodePalindromic Substrings საშუალო↗CSESLongest Palindrome საშუალო↗CSESAll Palindromes მოწინავე↗