In tiền tố dài nhất cũng là hậu tố của chuỗi trong C

Bài toán

Tìm độ dài tiền tố dài nhất của chuỗi mà đồng thời cũng là hậu tố (không tính toàn bộ chuỗi). Ví dụ: "abcab" → "ab" độ dài 2.

Ví dụ

"aabbccdaabbcc" → 6 ("aabbcc")
"abdab" → 2 ("ab")

Thuật toán (KMP prefix function)

• length = 0, i = n/2
• Duyệt i từ n/2 đến cuối
• Nếu str[i] == str[length]: length++, i++
• Nếu khác: length==0 ? i++ : length--
• Trả về length

Mã nguồn C

#include <stdio.h>

int longest(char str[], int n) {
    int len=0, i=n/2;
    if(n<2) return 1;
    while(str[i]) {
        if(str[i]==str[len]) { len++; i++; }
        else { if(len==0) i++; else len--; }
    }
    return len;
}

int main() {
    char str[] = "abccmmabcc";
    int n = sizeof(str)/sizeof(str[0]);
    printf("Length = %d", longest(str, n));
    return 0;
}

Kết quả

Length = 4 ("abcc")