Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

โปรแกรมค้นหาคำนำหน้าที่ยาวที่สุดที่เป็นคำต่อท้ายในภาษา 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 เมื่อฉัน

    • 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("helloworldhello"));
}

อินพุต

"helloworldhello"

ผลลัพธ์

hello