คำนำหน้าความสุขที่ยาวที่สุดใน C ++

สมมติว่าเรามีสตริง s เราต้องหาคำนำหน้าที่มีความสุขที่ยาวที่สุดของ s สตริงเรียกว่าคำนำหน้ามีความสุข หากเป็นคำนำหน้าที่ไม่ว่างเปล่าซึ่งเป็นส่วนต่อท้ายด้วย (ไม่รวมตัวเอง) หากไม่มีคำนำหน้าที่มีความสุขเช่นนั้น ให้คืนค่าสตริงว่าง

ดังนั้น หากอินพุตเป็นเหมือน "มาดาม" ผลลัพธ์จะเป็น "m" ซึ่งมี 4 คำนำหน้าไม่รวมตัวมันเอง เหล่านี้คือ "m", "ma", "mad", "mada" และคำต่อท้าย 4 ตัวเช่น "m", "am", "dam", "adam" คำนำหน้าที่ใหญ่ที่สุดซึ่งต่อท้ายด้วย "m" ด้วย

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน lps() ซึ่งจะใช้เวลา s

• n :=ขนาดของ s

• กำหนดขนาดของอาร์เรย์ n

• เจ :=0, ผม :=1

• ในขณะที่ฉัน

  • ถ้า s[i] เหมือนกับ s[j] แล้ว

    • ret[i] :=j + 1

    • (เพิ่ม i ขึ้น 1)

    • (เพิ่มขึ้น j โดย 1)

  • มิฉะนั้นเมื่อ s[i] ไม่เท่ากับ s[j] ดังนั้น −

    • ถ้า j> 0 แล้ว −

      • j :=ret[j - 1]

    • มิฉะนั้น

      • (เพิ่ม i ขึ้น 1)

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• n :=ขนาดของ s

• ถ้า n เท่ากับ 1 แล้ว −

  • ส่งคืนสตริงว่าง

• กำหนดอาร์เรย์ v =lps(s)

• x :=v[n - 1]

• ret :=สตริงว่าง

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ret :=ret + s[i]

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector <int> lps(string s){
      int n = s.size();
      vector<int> ret(n);
      int j = 0;
      int i = 1;
      while (i < n) {
         if (s[i] == s[j]) {
            ret[i] = j + 1;
            i++;
            j++;
         }
         else if (s[i] != s[j]) {
            if (j > 0)
               j = ret[j - 1];
            else {
               i++;
            }
         }
      }
      return ret;
   }
   string longestPrefix(string s) {
      int n = s.size();
      if (n == 1)
      return "";
      vector<int> v = lps(s);
      int x = v[n - 1];
      string ret = "";
      for (int i = 0; i < x; i++) {
         ret += s[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.longestPrefix("madam"));
}

อินพุต

"madam"

ผลลัพธ์

m