C Manacher's Algorithm: A Powerful Tool for Palindrome Detection 🎯

Welcome to our deep dive into the fascinating world of C Programming! Today, we'll explore the C Manacher's Algorithm, a powerful technique for detecting palindromes in strings. This algorithm is not only interesting but also useful in real-world applications. Let's get started!

Understanding the Basics 📝

What is a Palindrome?

A palindrome is a word, phrase, number, or any sequence of characters that reads the same backward as forward. For example, "racecar", "level", and "12321" are palindromes.

Why Manacher's Algorithm?

Manacher's Algorithm is an efficient solution for detecting palindromes in strings. It has a linear time complexity (O(n)) and requires constant extra space, making it a preferred choice over other brute-force methods.

Diving into Manacher's Algorithm 💡

The Manacher's Algorithm works by finding the center and radius of each palindrome in the given string. The algorithm maintains a center and a length for each palindrome, and as it iterates through the string, it updates these values to find larger palindromes.

Here's a simple example:

#include <stdio.h>

void printPalindrome(char *str, int start, int len) {
    printf("Palindrome found: ");
    for (int i = start - len; i <= start + len; i++) {
        if (i >= 0 && i < strlen(str))
            printf("%c", str[i]);
    }
    printf("\n");
}

int manacher(char *str) {
    int len = strlen(str);
    int P[len];
    int maxLen = 1, center = 0;

    for (int i = 1; i < len; i++) {
        P[i] = (i < maxLen) ? min(maxLen - i, P[2 * center - i]): 1;

        int right = i + P[i];
        while (right < len && str[right] == str[i - P[i]])
            P[i]++;

        if (i + P[i] > maxLen) {
            maxLen = i + P[i];
            center = i;
        }

        if (P[i] > maxLen / 2) {
            printf("Palindrome found at index %d with length %d\n", i - P[i]/2, 2 * P[i]);
        }
    }

    return maxLen;
}

int main() {
    char str[] = "racecarlevel";
    printf("Longest Palindrome found: %d\n", manacher(str));

    return 0;
}

In this example, we define a printPalindrome function to print a found palindrome and a manacher function that implements the Manacher's Algorithm. The main function initializes a string, calls the manacher function to find the longest palindrome, and prints the result.

Summary 📝

Today, we learned about the C Manacher's Algorithm, a powerful technique for detecting palindromes in strings. We discussed its importance, delved into its implementation, and saw a working example. Practice using this algorithm and see how it can enhance your C programming skills!

Stay tuned for more fascinating lessons on C Programming here at CodeYourCraft! 🙌

Happy coding! 💻🚀