সি প্রোগ্রামিং-এ স্ট্রিংয়ের লংগেস্ট প্রিফিক্স যা সুফিক্স ও আছে সেটি বের করা

একটি স্ট্রিং দেওয়া থাকলে, সেটির সবচেয়ে লম্বা প্রিফিক্স (prefix) বের করতে হবে যা স্ট্রিংয়ের সুফিক্স (suffix) ও একই। যেমন "abcab" স্ট্রিংয়ে "ab" দৈর্ঘ্য ২ এবং এটি সবচেয়ে বড় সাবস্ট্রিং যেটি প্রিফিক্স ও সুফিক্স উভয়।

উদাহরণ

Input: str[] = "aabbccdaabbcc"
Output: 6

Input: abdab
Output: 2

অ্যাপ্রোচ: স্ট্রিংয়ের শুরু এবং শেষ থেকে পয়েন্টার শুরু করলে ওভারল্যাপ হবে। বরং স্ট্রিংকে মাঝপথ থেকে ভাগ করে লেফট এবং রাইট পার্ট মিলিয়ে দেখা হয়। সমান হলে দৈর্ঘ্য রিটার্ন, নাহলে ছোট দৈর্ঘ্যে চেষ্টা করা হয়।

অ্যালগরিদম

int longest(char str[], int n)
START
STEP 1: DECLARE length = 0, i = n/2
STEP 2: IF n < 2 RETURN 1
STEP 3: WHILE str[i] != '\0'
    IF str[i] == str[length] THEN length++, i++
    ELSE
        IF length == 0 THEN i++
        ELSE length--
    END IF
END WHILE
RETURN length
STOP

সি প্রোগ্রাম

#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