สตริงย่อยที่ซ้ำกันที่ยาวที่สุดใน C++

สมมติว่าเรามีสตริง S ให้พิจารณาสตริงย่อยที่ต่อเนื่องกันที่ซ้ำกันทั้งหมดที่เกิดขึ้น 2 ครั้งขึ้นไป (เหตุการณ์อาจทับซ้อนกัน) เราต้องหาสตริงย่อยที่ซ้ำกันซึ่งมีความยาวมากที่สุด หากไม่มีสตริงย่อยดังกล่าว ให้ส่งคืนสตริงว่าง เนื่องจากคำตอบอาจมีขนาดใหญ่มาก ดังนั้นให้กลับมาใน mod 10^9 + 7

ดังนั้น หากอินพุตเป็นเหมือน "ababbaba" ผลลัพธ์จะเป็น "bab"

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

• ม :=1e9 + 7

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

• กลับ ((a mod m) + (b mod m)) mod m

• กำหนดฟังก์ชั่นย่อย () สิ่งนี้จะใช้เวลา a, b,

• return ((a mod m) - (b mod m) + m) mod m

• กำหนดฟังก์ชัน mul() ซึ่งจะใช้ a, b,

• กลับ ((a mod m) * (b mod m)) mod m

• กำหนดกำลังอาร์เรย์

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

• ถ้า x เท่ากับ 0 แล้ว −

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

• กำหนดหนึ่งแผนที่ที่เรียกว่าแฮช

• ปัจจุบัน :=0

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

  • ปัจจุบัน :=add(mul(current, 26), s[i] - 'a')

• hash[current] :=กำหนดอาร์เรย์ (1, 0)

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

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

  • ปัจจุบัน :=sub(กระแส, mul(กำลัง[x - 1], s[i - x] - 'a'))

  • ปัจจุบัน :=add(mul(current, 26), s[i] - 'a')

  • ถ้า count เป็นสมาชิกของ hash แล้ว −

    • สำหรับทั้งหมดในแฮช[ปัจจุบัน] -

      • ถ้าสตริงย่อยของ s จากมันถึง x - 1 เหมือนกับสตริงย่อยของ s จาก i - x + 1 ถึง x- 1 ดังนั้น −

        • ส่งคืนสตริงย่อยของ s จากมันเป็น x - 1

  • มิฉะนั้น

    • ใส่ i - x + 1 ที่ท้าย hash[current]

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

• จากวิธีหลัก ให้ทำดังนี้ −

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

• n :=ขนาด S

• power :=กำหนดอาร์เรย์ขนาด n และเติมด้วย 1

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

  • พลัง[i] :=mul(พลัง[i - 1], 26)

• ต่ำ :=0, สูง :=n - 1

• ในขณะที่ต่ำ <=สูง ทำ -

  • กลาง :=ต่ำ + (สูง - ต่ำ) /2

  • temp :=ok(กลาง, S)

  • ถ้าขนาดของอุณหภูมิเท่ากับ 0 แล้ว −

    • สูง :=กลาง - 1

  • มิฉะนั้น

    • ถ้า size of temp> size of ret แล้ว −

      • ret :=อุณหภูมิ

    • ต่ำ :=กลาง + 1

• รีเทิร์น

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int m = 1e9 + 7;
   int add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   int sub(lli a, lli b){
      return ((a % m) - (b % m) + m) % m;
   }
   int mul(lli a, lli b){
      return ((a % m) * (b % m)) % m;
   }
   vector<int> power;
   string ok(int x, string s){
      if (x == 0)
      return "";
      unordered_map<int, vector<int> > hash;
      lli current = 0;
      for (int i = 0; i < x; i++) {
         current = add(mul(current, 26), s[i] - 'a');
      }
      hash[current] = vector<int>(1, 0);
      int n = s.size();
      for (int i = x; i < n; i++) {
         current = sub(current, mul(power[x - 1], s[i - x] -
         'a'));
         current = add(mul(current, 26), s[i] - 'a');
         if (hash.count(current)) {
            for (auto& it : hash[current]) {
               if (s.substr(it, x) == s.substr(i - x + 1, x)) {
                  return s.substr(it, x);
               }
            }
         } else {
            hash[current].push_back(i - x + 1);
         }
      }
      return "";
   }
   string longestDupSubstring(string S){
      string ret = "";
      int n = S.size();
      power = vector<int>(n, 1);
      for (int i = 1; i < n; i++) {
         power[i] = mul(power[i - 1], 26);
      }
      int low = 0;
      int high = n - 1;
      while (low <= high) {
         int mid = low + (high - low) / 2;
         string temp = ok(mid, S);
         if (temp.size() == 0) {
            high = mid - 1;
         } else {
            if (temp.size() > ret.size())
            ret = temp;
            low = mid + 1;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.longestDupSubstring("ababbaba"));
}

อินพุต

"ababbaba"

ผลลัพธ์

bab