RioTian

用户名：jiahe

访问量：34655

签　名：

2021加油

等　　级
排　　名	76
经　　验	9895
参赛次数	2
文章发表	78
年　　龄	0
在职情况	学生
学　　校	XX理工大学
专　　业	软件工程

　　自我简介：

个人博客：https://www.cnblogs.com/RioTian/

TA的其他文章

Kanna-九宫幻方深度理解-C++
浏览：563

Kanna-最长公共子序列-C++
浏览：345

后缀子串排序-题解(C++代码)
浏览：377

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

Kanna-密码截获-(C++代码)

　　作者: RioTian　　　　发表时间：2020-01-15 14:22:52 浏览：289　|　评论：0　

原题链接：密码截获

求字符串中的最大回文，最好的算法应该就是Manacher算法（马拉车算法）
https://www.cnblogs.com/Kanna/articles/12196564.html
参考网站

#include <iostream>  
    #include <cstring>
    #include <algorithm>  
    #include<cstdlib>//好奇不加这个竟然不让我通过
	
    using namespace std;
    char s[1000];
    char s_new[2000];
    int  p[2000];
    /*-----------------------------------------------------------*/
    int Init()
    {
        int len = strlen(s);
        s_new[0] = '$';//防止越界
        s_new[1] = '#';
        int j = 2;
        //处理字符串，这样无论是奇字符串还是偶字符串都能变成奇字符串
        for (int i = 0; i < len; i++)
        {
            s_new[j++] = s[i];
            s_new[j++] = '#';
        }
        s_new[j] = '\0';//手动补上
        return j;//j此时就是s_new的长度
    }
    /*-----------------------------------------------------------*/
    int Manacher()
    {
        int len = Init();
        int max_len = -1;
        int id;
        int mx = 0;
        for (int i = 1; i < len; i++)//不从0开始
        {
            if (i < mx)
                p[i] = min(p[2 * id - i], mx - i);//2*id-i是i关于id的对称点 j
            else
                p[i] = 1;
            while(s_new[i - p[i]] == s_new[i + p[i]])
                p[i]++;
            if (mx < i + p[i])
            {
                id = i;
                mx = i + p[i];
            }
            max_len = max(max_len, p[i] - 1);
        }
        return max_len;
    }
    /*-----------------------------------------------------------*/
    int main()
    {
        while (scanf("%s", s)!=EOF)
        {
            printf("%d\n", Manacher());
        }
    }

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

RioTian

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）

C二级辅导-阶乘数列（C语言代码）

人见人爱A+B （C语言代码）

Kanna-密码截获-(C++代码)

评论区

精彩推荐

The 3n + 1 problem （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C二级辅导-进制转换（C语言代码）

假币问题（C++代码）（向上取整的一种处理方式）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

K-进制数（C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

RioTian

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）

C二级辅导-阶乘数列 （C语言代码）

人见人爱A+B （C语言代码）

Kanna-密码截获-(C++代码)

评论区

精彩推荐

The 3n + 1 problem （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C二级辅导-进制转换 （C语言代码）

假币问题 （C++代码）（向上取整的一种处理方式）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

K-进制数 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-阶乘数列（C语言代码）

　　评论区

C二级辅导-进制转换（C语言代码）

假币问题（C++代码）（向上取整的一种处理方式）

C二级辅导-分段函数（C语言代码）

K-进制数（C++代码）