G - 签到题

62 阅读 0 评论 41 点赞

我是靠谱客的博主淡定山水，最近开发中收集的这篇文章主要介绍G - 签到题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Description

回文串大家都知道是什么吧~

现在给你一串字符串

请求出该字符串最长的连续非回文子串的长度是多少。

Input

长度不超过10^6。题目保证字符串只由小写字母a-z组成。

Output

一个整数，表示最长非回文串的长度。若不存在输出-1。

Sample Input

AAABA

Sample Output

当时自己曾今设想过情况的分析，没有细化，我只是想到，如果存在什么什么样的情况，自己的条件是不成立的，至于细节，我们只是拿样例来否定我们的方法，现在来看看存在一定的缺陷。我们的时间复杂度，当时分析的是，如果我们利用尺取的方法的话，我们就能做出来了，但是自己并不知道怎样来尺取，所以就留给自己一个我可以不会的借口，又想到我们没有做他们的题，他们肯定做过，好了，这么多的借口，足够了，好的，你自己说的，现在学会尺取，和做他们的题。

好了，分析一下题。如果它是回文串的话，我们可不可以只看一半，发现不可以，为什么不可以，因为可能出现，超过一半的和另一半的一部分组合，所以不可以。如果不是回文串的话，自然就是长度了。那么，我想到了，尺取，想到时间复杂度小一点，应该就能过了，他们肯定学了什么诀窍。那有这么多诀窍，就算人家做了，这是你感到自豪的地方么，是你的耻辱啊，你玩的时间，人家都用来了学习，编程，你在干什么啊，醒醒吧。人家的努力，一点一点，就能灭掉你了。别再狂妄了。

如果相同的话，aaaaaa,这种情况自然是0

如果是回文串里有不同的字母，那么中间肯定有一个，aaa.b..aa...aaa, 不管顺序的话，你想想，我们去掉一个字符的话，是不是一定会导致不能匹配，这样是不是就是完成了题目的要求。

#include<cstdio>
#include<cstring>
const int maxn=1e6+10;
char str[maxn];

int main()
{
    while(~scanf("%s",str)){
        int len=strlen(str);
        char temp=str[0];
        int flag=1;
        for(int i=1;i<len;i++)
            if(str[i]!=temp){
                flag=0;
                break;
            }
        if(flag||len==1){
            printf("-1n");
            continue;
        }
        flag=1;
        int i=0,j=len-1;
        while(i<j){
            if(str[i]==str[j]){
                i++;
                j--;
            }
            else{
                 flag=0;
                break;
            }
        }
        if(!flag)
             printf("%dn",len);
        else
            printf("%dn",len-1);
    }
    return 0;
}