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

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

Suffix ของสตริง str คือสตริงทั้งหมดที่สร้างขึ้นจากการตัดตัวอักษรนำหน้าของสตริงออก

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

ในขณะที่ str1 = 'abca' และ str2 = 'ca' คือ 0 เพราะเรานับจากต้นทาง

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต − str = 'xyxyx'

เอาต์พุต −

คำอธิบาย − ทุก substring และความคล้ายคลึงของสตริงกับ suffix ทั้งหมด คือ −

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

เพื่อแก้ปัญหานี้ เราจะใช้ Z-algorithm และคำนวณ Z-array Z-array คืออาร์เรย์ที่มีความยาวเท่ากับความยาวของสตริง ทุกองค์ประกอบเก็บความยาวของ prefix ของ 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