หาการเลื่อนขั้นต่ำสำหรับคำนำหน้าร่วมยาวที่สุดใน C++

พิจารณาว่ามีสตริงสองตัว A และ B ความยาวของ A และ B เท่ากัน ในการเลื่อน (Shift) หนึ่งครั้ง เราสามารถหมุนสตริง B หนึ่งองค์ประกอบ เราต้องหาการเลื่อนขั้นต่ำที่จำเป็นเพื่อให้ได้คำนำหน้าร่วม (Common Prefix) ยาวที่สุดจาก A และ B ดังนั้นถ้า A = "computerprogramming" และ B = "programminglanguage" การเลื่อนขั้นต่ำคือ 8 และคำนำหน้าคือ "programming"

สมมติว่าเราเพิ่มสตริง B ที่ท้ายของ B เอง ดังนั้น B = B + B แล้วไม่ต้องหาคำนำหน้าของแต่ละการเลื่อนแยกกัน ดังนั้นเราต้องหาคำนำหน้ายาวที่สุดของ A ที่มีอยู่ใน B และตำแหน่งเริ่มต้นของคำนำหน้าใน B จะให้จำนวนการเลื่อนที่แท้จริง

ตัวอย่าง

#include <iostream> 
using namespace std; 

void KhuthMorrisPatt(int m, int n, string B, string A) {
    int pos = 0, len = 0;
    int p[m + 1];
    int k = 0;
    p[1] = 0;
    for (int i = 2; i <= n; i++) {
        while (k > 0 && A[k] != A[i - 1])
            k = p[k];
        if (A[k] == A[i - 1])
            ++k;
        p[i] = k;
    }
    for (int j = 0, i = 0; i < m; i++) {
        while (j > 0 && A[j] != B[i])
            j = p[j];
        if (A[j] == B[i])
            j++;
        if (j > len) {
            len = j;
            pos = i - j + 1;
        }
    }
    cout << "Shift = " << pos << endl;
    cout << "Prefix = " << A.substr(0, len);
}

int main() {
    string A = "programminglanguage";
    string B = "computerprogramming";
    int n = A.size();
    B = B + B;
    KhuthMorrisPatt(2 * n, n, B, A);
}

ผลลัพธ์

Shift = 8
Prefix = programming