专栏首页Don的成长史【GPLT】L2-008 最长对称子串

【GPLT】L2-008 最长对称子串

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/88807953

题目描述:

对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。

输入描述:

输入在一行中给出长度不超过1000的非空字符串。

输出描述:

在一行中输出最长对称子串的长度。

输入样例:

Is PAT&TAP symmetric?

输出样例:

11

解题思路:

我一开始的思路就是暴力破解,用ans来记录最长对称子串的长度,然后通过无脑遍历翻转所有子串来寻找对称子串,不断更新ans最后输出。提交代码之后直接TLE...25分得了17分。嗯,然后我换了个思路,从后往前找第一个相同的字符,找到后就用t2往前、t1往后来寻找对称子串,直到字符不相等或者t1、t2相遇为止。

AC代码:TLE代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str;
    getline(cin,str);
    int len = str.length();
    int ans = -1e5;   //用来记录最长对称子串的长度
    for(int i = 0; i < len; i++)
    {
        string s1 = "";
        for(int j = i; j < len; j++)
        {
            s1 = str.substr(i,j);
            string s2 = s1;
            reverse(s2.begin(),s2.end());  //将字符串翻转
            if(s1 == s2)   //若字符串对称
            {
                int temp = s1.length();
                ans = max(ans,temp);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str;
    getline(cin,str);
    int len = str.length();
    int ans = 1;   //用来记录最长对称子串的长度
    for(int i = 0; i < len-1; i++)
    {
        for(int j = len-1; j >= i; j--)
        {
            if(str[i] == str[j])   //从后往前找第一个相同字符
            {
                int t1 = i, t2 = j;
                bool flag = true;    //用来记录是不是对称字符串
                while(t1 <= t2)   //判断是不是对称字符串
                {
                    t1++;
                    t2--;
                    if(str[t1] != str[t2])   //若不是对称字符串
                    {
                        flag = false;
                        break;
                    }
                }
                if(flag)
                {
                    ans = max(ans,j-i+1);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【蓝桥杯】ADV-73 数组输出

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【PAT乙级】单身狗

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【GPLT】L1-039 古风排版

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • Codeforces Round #505 C. Plasticine zebra(思维)

    题目链接:http://codeforces.com/contest/1025/problem/C

    Ch_Zaqdt
  • cookie、session和中间件

    cookie是保存在浏览器上的键值对,session是保存在服务端的键值对,cookie和session存在的目的是保存用户的登录状态,那么为什么有cookie...

    GH
  • Express中间件的使用、原理及实现

    现在在一些企业里用nodejs做服务端开发已经很普遍了,这里面最火的框架当然要数express了,express将nodejs原生的支持的http模块进行了简单...

    挥刀北上
  • Asp.Net Core中的静态文件-12

    在这个视频中我们将讨论如何使 ASP.NET Core 应用程序,支持静态文件,如 HTML,图像,CSS 和 JavaScript 文件。

    角落的白板报
  • JavaScript 设计模式学习第二十九篇- 中间件

    (Middleware),又称中介层,是提供系统软件和应用软件之间连接的软件,以便于软件各部件之间的沟通,特别是应用软件对于系统软件的集中的逻辑。中间件在企业架...

    越陌度阡
  • 每天一道剑指offer-矩形中的路径

    请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个...

    乔戈里
  • ASP.NET Core开发人员异常页面-13

    如果我们使用上面的代码运行我们的应用程序,我们看不到异常,而是看到“来自 Default.html 页面中的 Hello”。如果您了解 asp.net Core...

    角落的白板报

扫码关注云+社区

领取腾讯云代金券