โปรแกรม C หา Prefix ที่ยาวที่สุดซึ่งเป็น Suffix เดียวกันของสตริง

โจทย์

กำหนดสตริง หาความยาวของ Prefix (คำนำหน้า) ที่ยาวที่สุด ซึ่งก็คือ Suffix (คำท้าย) ของสตริงเดียวกันนั้น

ตัวอย่าง

Input: "aabbccdaabbcc"  Output: 6  ("aabbcc")
Input: "abdab"          Output: 2  ("ab")

อัลกอริทึม (KMP-inspired)

1. เริ่มเปรียบเทียบจากกลางสตริง: i = n/2, length = 0
2. while str[i] != '\0':
3. ถ้า str[i] == str[length]: length++, i++
4. ถ้าไม่เท่ากัน: ถ้า length==0 → i++ มิฉะนั้น length--
5. คืนค่า length

วิธีนี้หลีกเลี่ยงการเปรียบเทียบซ้ำซ้อน ใช้แนวคิดคล้าย KMP failure function

โค้ดภาษา C

#include <stdio.h>

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

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

ผลลัพธ์

Length = 4

อธิบาย: สตริง "abccmmabcc" มี prefix "abcc" (ความยาว 4) ซึ่งก็คือ suffix "abcc" เช่นกัน