ผลรวมของความคล้ายคลึงของสตริงที่มีส่วนต่อท้ายทั้งหมดใน C++

ในปัญหานี้เราได้รับสตริง str งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของความคล้ายคลึงของสตริงที่มีส่วนต่อท้ายทั้งหมด

คำต่อท้ายของสตริง str คือสตริงทั้งหมดที่สร้างขึ้นโดยการกำจัดอักขระเริ่มต้นของสตริง

ความคล้ายคลึงของสตริง str1 และ str2 คือความยาวของคำนำหน้าที่ยาวที่สุดที่เหมือนกันสำหรับทั้งสตริง ตัวอย่างเช่น str1 ='abbac' และ str2 ='abb' คือ 3

ขณะที่ str1 ='abca' และ str2 ='ca' เป็น 0 เมื่อเรานับตั้งแต่เริ่มต้น

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − str =‘xyxyx’

ผลผลิต −

คำอธิบาย − สตริงย่อยและความคล้ายคลึงทั้งหมดของสตริงที่มีส่วนต่อท้ายทั้งหมดคือ −

‘xyxyx’ -> 5
‘yxyx’ -> 0
‘xyx’ -> 3
‘yx’ -> 0
‘x’ -> 1
Sum = 5 + 0 + 3 + 0 + 1 = 9

เพื่อแก้ปัญหานี้ เราจะใช้ Z-algorithm และคำนวณ Z-array Z-array คืออาร์เรย์ของความยาวเท่ากับความยาวของสตริง ทุกองค์ประกอบเก็บคำนำหน้าของ str โปรแกรมด้านล่างแสดงการนำไปใช้

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
void createZArray(string str, int n, int Zarray[]) {
   int L, R, k;
   L = R = 0;
   for (int i = 1; i < n; ++i) {
      if (i > R) {
         L = R = i;
         while (R < n && str[R - L] == str[R])
            R++;
         Zarray[i] = R - L;
         R--;
      }
      else {
         k = i - L;
         if (Zarray[k] < R - i + 1)
         Zarray[i] = Zarray[k];
         else {
            L = i;
            while (R < n && str[R - L] == str[R])
            R++;
            Zarray[i] = R - L;
            R--;
         }
      }
   }
}
int calSumSimilarities(string s, int n) {
   int Zarray[n] = { 0 };
   createZArray(s, n, Zarray);
   int total = n;
   for (int i = 1; i < n; i++)
      total += Zarray[i];
   return total;
}
int main() {
   string s = "xyxyx";
   int n = s.length();
   cout<<"Sum of similarities of string with all of its suffixes is "<<calSumSimilarities(s, n);
   return 0;
}

ผลลัพธ์

Sum of similarities of string with all of its suffixes is 9