C語言字符串中的最長回文子串

發(fā)布時間：2024-08-30 14:25:37 來源：億速云閱讀：80 作者：小樊欄目：編程語言

在C語言中，要找到一個字符串中的最長回文子串，可以使用動態(tài)規(guī)劃的方法

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

void longestPalindromicSubstring(char *str) {
    int n = strlen(str);
    int maxLength = 0;
    int start = 0;
    int dp[n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (str[i] == str[j] && (i - j < 2 || dp[j + 1][i - 1])) {
                dp[j][i] = 1;
                if (i - j + 1 > maxLength) {
                    maxLength = i - j + 1;
                    start = j;
                }
            } else {
                dp[j][i] = 0;
            }
        }
    }

    printf("最長回文子串: ");
    for (int i = start; i< start + maxLength; i++) {
        printf("%c", str[i]);
    }
    printf("\n");
}

int main() {
    char str[] = "babad";
    longestPalindromicSubstring(str);
    return 0;
}

這段代碼首先定義了一個二維數(shù)組dp，用于存儲字符串中每個子串是否為回文子串。然后遍歷字符串，對于每個字符，檢查以該字符結(jié)尾的子串是否為回文子串。如果是，則更新最長回文子串的長度和起始位置。最后，輸出最長回文子串。

注意：這個代碼示例僅適用于ASCII字符集。對于其他字符集，可能需要進行相應(yīng)的修改。

向AI問一下細節(jié)

C語言字符串中的最長回文子串

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標簽