第六十六练 最长回文子串 - Manacher算法

#include <stdio.h>
#include <string.h>
#include <math.h>

#define PRIME 101 // A prime number used in the hash function

int rabinKarpSearch(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int i, j;
    int hash_pattern = 0; // Hash value for the pattern
    int hash_text = 0;    // Hash value for the current text window
    int h = 1;

    // Calculate h, which is the hash value for the next window of text
    for (i = 0; i < m - 1; i++) {
        h = (h * 256) % PRIME;
    }

    // Calculate the initial hash values for the pattern and the first window of text
    for (i = 0; i < m; i++) {
        hash_pattern = (256 * hash_pattern + pattern[i]) % PRIME;
        hash_text = (256 * hash_text + text[i]) % PRIME;
    }

    // Slide the pattern over the text one position at a time and check for a match
    for (i = 0; i <= n - m; i++) {
        if (hash_pattern == hash_text) {
            // If the hash values match, perform a character-by-character comparison
            for (j = 0; j < m; j++) {
                if (text[i + j] != pattern[j]) {
                    break;
                }
            }
            if (j == m) {
                return i; // Match found, return the starting index
            }
        }

        // Calculate the hash value for the next window of text
        if (i < n - m) {
            hash_text = (256 * (hash_text - text[i] * h) + text[i + m]) % PRIME;
            if (hash_text < 0) {
                hash_text += PRIME; // Ensure the hash value is non-negative
            }
        }
    }

    return -1; // No match found
}

int main() {
    char text[100], pattern[100];

    printf("Enter the text string: ");
    scanf("%s", text);

    printf("Enter the pattern string: ");
    scanf("%s", pattern);

    int result = rabinKarpSearch(text, pattern);

    if (result != -1) {
        printf("Match found at index %d\n", result);
    } else {
        printf("No match found\n");
    }

    return 0;
}