Tổng các điểm tương đồng của chuỗi với tất cả các hậu tố của nó trong C ++

Trong bài toán này, chúng ta được cung cấp chuỗi str. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng các điểm tương đồng của chuỗi với tất cả các hậu tố của nó.

Các hậu tố của chuỗi str là tất cả các chuỗi được tạo bằng cách loại bỏ các ký tự bắt đầu của chuỗi.

Điểm giống nhau của chuỗi str1 và str2 là độ dài của tiền tố dài nhất chung cho cả chuỗi. Ví dụ:str1 =‘abbac’ và str2 =‘abb’ là 3.

Trong khi str1 =‘abca’ và str2 =‘ca’ là 0. Khi chúng tôi đếm từ đầu.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - str =‘xyxyx’

Đầu ra -

Giải thích - Tất cả các chuỗi con và các điểm tương tự của chuỗi với tất cả các hậu tố là -

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

Để giải quyết vấn đề này, chúng ta sẽ sử dụng thuật toán Z và tính toán mảng Z. Z-array là một mảng có độ dài bằng độ dài của chuỗi. Mỗi phần tử lưu trữ một tiền tố của str. Chương trình dưới đây cho thấy việc triển khai,

Ví dụ

#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;
}

Đầu ra

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