美文网首页
回文子串个数

回文子串个数

作者: IceFrozen | 来源:发表于2019-01-19 12:48 被阅读0次

注意子串和子序列的区别
子串:必须连续
子序列:可以不连续
两者都可以包含字符串本身

解法一:暴力求解
#include <stdio.h>
#include <string.h>
#include <malloc.h>

_Bool palindrome (char *str) {    //判断一个字符串是否回文
    int tag = 1;
    for (int i = 0, len = strlen(str); i <= len / 2; i++) {
        if (str[i] != str[len - i - 1])
            tag = 0;
    }
    if (tag)
        return 1;
    else 
        return 0;
}

int subPalindromeNum (char *str) {    //计算回文子串个数
    int len = strlen(str);
    int count = 0;    //记录回文子串个数
    for (int i = 0; i < len; i++)    //遍历每一个子串
        for (int j = i; j < len; j++) {
            int n = 0;
            char *temp = (char *) malloc (sizeof(char) * (j - i + 2));    //拷贝遍历过程中的每一个字符串
            for (int k = i; k <= j; k++)
                temp[n++] = str[k];
            temp[n] = '\0';
            if (palindrome(temp))
                count++;
            free(temp);
        }
    return count;
}

int main() {
    for (char str[1000]; ~scanf("%s", &str);)
        printf("%d\n", subPalindromeNum(str));
    return 0;
}
解法二:动态规划
#include <stdio.h>
#include <malloc.h>
#include <string.h>

int subPlalindromeNum (char *str, int len) {
    if (len == 0)
        return 0;
    int count = 0;    //记录结果
    int **dp = (int **) malloc (sizeof(int *) * len);    //动态分配二维 dp 数组并初始化为 0
    for (int i = 0; i < len; i++) {
        dp[i] = (int *) malloc (sizeof(int) * len);
        for (int j = 0; j < len; j++) {
            dp[i][j] = 0;
        }
    }
    for (int i = 0; i < len; i++) {    //第二个循环在遍历第一个循环已经遍历过的字符,保证了 dp 数组的有效性
        dp[i][i] = 1;
        count++;
        for (int j = i - 1; j >= 0; j--)
            if (str[i] == str[j])    //判断首尾是否相等
                if (i - 1 == j || dp[i - 1][j + 1]) {    //首尾连续或者去掉首尾是回文,则计数
                    dp[i][j] = 1;
                    count ++;
                }
    }
    free(dp);
    return count;
}

int main() {
    for (char str[10000]; ~scanf("%s", str);)
        printf("%d\n", subPlalindromeNum(str, strlen(str)));
    return 0;
}

相关文章

  • 回文子串个数

    给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串,即使是由相同的字符组...

  • 回文子串个数

    注意子串和子序列的区别子串:必须连续子序列:可以不连续两者都可以包含字符串本身 解法一:暴力求解 解法二:动态规划

  • 最长回文子串

    判断是否是回文字符串 获取所有可能子串 获取所有回文子串 进阶

  • LeetCode 第647题:回文子串

    1、前言 2、思路 此题与最长回文子串很像,只不过那个是求最长的回文子串,而这个是求回文子串的数目。但是他们的解法...

  • 最长回文子串

    最长回文子串——Manacher 算法 1. 问题定义 最长回文字符串问题:给定一个字符串,求它的最长回文子串长度...

  • C语言实现求最长回文子串

    最长回文子串的概念 回文串是指正序和反序都一样的字符串,例如:Str1 = "AbbA",则Str1的最长回文子串...

  • 打卡-最长回文子串

    最长回文子串(中等)

  • 最长回文子序列

    该问题区别于最长回文子串,子串必须是连续的,而子序列则可以跳跃,例如AABCAA的最长回文子串为AA,但是它的最长...

  • 最长回文子串杀器-马拉车算法 2020-09-07(未允禁转)

    1.求解最长回文子串 在之前博客中提到解决回文串问题时,是利用了大回文串 = 小回文串向两头扩展的性质得到状态转移...

  • Manacher's Algorithm算法分析Java

    Manacher's Algorithm俗称马拉车算法,对于求字符串中最长回文子串效率极高。 在求最长回文子串的时...

网友评论

      本文标题:回文子串个数

      本文链接:https://www.haomeiwen.com/subject/ljoadqtx.html