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

int ai, aj;                     // ai and aj to store the value of i and j respectively
int maxx(int a, int b) {        // to return max of the two numbers
    return (a <= b) ? b : a;
}

void LongestPal(char a[], int n) {    // to find longest palindrome
    int i, j, max = 0;
    int p[1000][1000] = { 0 };

    for (j = 0; j < n; j++)
        for (i = 0; i <= j; i++) {
            if (i == j) {       // for one string having only one character
                p[i][j] = 1;
                if (max < p[i][j]) {
                    max = p[i][j];
                    ai = i;
                    aj = j;
                }
            }
            if (j == (i + 1)) {   // for string having two characters
                if (a[i] == a[j]) {  // if the string is like "aa","bb" etc.
                    p[i][j] = 2;
                    if (max < p[i][j]) {
                        max = p[i][j];
                        ai = i;
                        aj = j;
                    }
                } else {       // if string like "ab","ba" etc.
                    p[i][j] = 1;
                    if (max < p[i][j]) {
                        max = p[i][j];
                        ai = i;
                        aj = j;
                    }
                }
            } else {        // for all other type of strings
                if (a[i] == a[j]) {   // if a longer palindrome found
                    p[i][j] = p[i-1][j-1] + 2;
                    if (max < p[i][j]) {
                        max = p[i][j];
                        ai = i;
                        aj = j;
                    }
                } else {   // if no longer palindrome is present
                    p[i][j] = maxx(p[i+1][j], p[i][j-1]);
                    if (max < p[i][j]) {
                        max = p[i][j];
                        ai = i;
                        aj = j;
                    }
                }
            }
        }
}

int main() {
    int i, j, n;
    char a[1000];

    printf("Just enter the string hoss!\n");
    scanf("%s", &a);
    n = strlen(a);
    LongestPal(a, n);
    for (i = ai; i <= aj; i++)
        printf("%c", a[i]);

    return 0;
}

在这个程序中，我想找到最长的回文子序列，但无法运行程序

我为每个案例写了评论

这个打印最长回文子序列的程序不起作用，当我运行它时，Windows 控制台在输入后停止工作。

4

1 回答 1

1

您的程序失败，因为它使用自动存储（也称为堆栈）分配了太多数据。 int p[1000][1000]使用 4MB，对于您的系统默认堆栈大小来说可能太多了。您可以通过将此数组分配为：

int p[n][n];

这在 C99 中是允许的，但您的编译器可能不支持 C99。

你的算法有点复杂。为什么不枚举所有位置，如果你在那里有一个回文i并j跟踪最长的一个，只需使用辅助函数进行验证：

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

int isPalindrome(const char *a, int i, int j) {
    for (; i < j; i++, j--) {
        if (a[i] != a[j])
            return 0;
    }
    return 1;
}

void getLongestPalindrome(const char *a, int n, int *ai, int *aj) {
    int i, j, maxi, maxj;

    for (maxi = maxj = i = 0; i < n; i++) {
        for (j = n - 1; j > i + maxj - maxi; j--) {
            if (isPalindrome(a, i, j)) {
                maxi = i;
                maxj = j;
                break;
            }
        }
    }
    *ai = maxi;
    *aj = maxj;
}

int main(void) {
    char a[1000];
    int i, j;

    printf("Enter the string: ");
    if (scanf("%999s", a) == 1) {
        getLongestPalindrome(a, strlen(a), &i, &j);
        printf("longest palindrome at %d..%d: %.*s\n", i, j, j - i + 1, a + i);
    }
    return 0;
}
于 2016-08-15T15:56:23.033 回答