深入探索字符串算法：C语言实现字符串匹配与最长回文子串

蔚落 2023-10-14 22:01 40阅读 0赞

## 深入探索字符串算法：C语言实现字符串匹配与最长回文子串 ##

字符串算法在计算机科学中占据重要地位，它们在文本处理、数据分析和搜索等领域发挥着关键作用。本篇博客将深入介绍两种常见的字符串算法：字符串匹配和最长回文子串，以及在C语言中的实现示例。

### 字符串匹配 ###

字符串匹配是指在一个主串中查找一个子串的过程，如果找到匹配的子串，就返回它的位置。下面是KMP字符串匹配算法的C语言实现示例：

#include <stdio.h>
    #include <string.h>
    
    void computeLPSArray(char* pattern, int M, int* lps) {
        int length = 0;
        lps[0] = 0;
    
        int i = 1;
        while (i < M) {
            if (pattern[i] == pattern[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
    
    void KMPSearch(char* text, char* pattern) {
        int N = strlen(text);
        int M = strlen(pattern);
    
        int lps[M];
        computeLPSArray(pattern, M, lps);
    
        int i = 0, j = 0;
        while (i < N) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            }
    
            if (j == M) {
                printf("Pattern found at index %d\n", i - j);
                j = lps[j - 1];
            } else if (i < N && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
    }
    
    int main() {
        char text[] = "ABABDABACDABABCABAB";
        char pattern[] = "ABABCABAB";
    
        printf("Text: %s\n", text);
        printf("Pattern: %s\n", pattern);
        printf("Pattern found at positions:\n");
        KMPSearch(text, pattern);
    
        return 0;
    }

### 最长回文子串 ###

最长回文子串是一个正读和反读都一样的字符串片段。下面是最长回文子串问题的C语言实现示例：

#include <stdio.h>
    #include <string.h>
    
    int max(int a, int b) {
        return (a > b) ? a : b;
    }
    
    int longestPalindromeSubstr(char* str) {
        int n = strlen(str);
        int dp[n][n];
    
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
    
        int maxLength = 1;
        int start = 0;
    
        for (int cl = 2; cl <= n; cl++) {
            for (int i = 0; i < n - cl + 1; i++) {
                int j = i + cl - 1;
    
                if (str[i] == str[j] && cl == 2) {
                    dp[i][j] = 2;
                    if (cl > maxLength) {
                        maxLength = cl;
                        start = i;
                    }
                } else if (str[i] == str[j] && dp[i + 1][j - 1] == cl - 2) {
                    dp[i][j] = cl;
                    if (cl > maxLength) {
                        maxLength = cl;
                        start = i;
                    }
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
    
        printf("Longest Palindrome Substring: ");
        for (int i = start; i < start + maxLength; i++) {
            printf("%c", str[i]);
        }
        printf("\n");
    
        return maxLength;
    }
    
    int main() {
        char str[] = "forgeeksskeegfor";
    
        printf("Input string: %s\n", str);
        printf("Length of Longest Palindrome Substring: %d\n", longestPalindromeSubstr(str));
    
        return 0;
    }

### 总结 ###

本篇博客深入探讨了字符串算法中的两个重要问题：字符串匹配和最长回文子串。通过C语言实现的示例代码，您可以更好地理解这些问题的解法和应用。字符串算法在文本搜索、编译器设计、自然语言处理等领域具有广泛的应用，掌握这些算法将有助于您解决各种实际问题。