美文网首页
最长回文串子串 渣渣版

最长回文串子串 渣渣版

作者: 三三At你 | 来源:发表于2017-05-11 21:35 被阅读0次
#include<iostream>  
#include<cstdio>  
#include<string>  
using namespace std;  
  
int main()  
{  
    int n,l,r,pos,maxlen;  
    string str;  
    cin>>n;  
    while(n--)  
    {  
        cin>>str;  
        for(int i=0;i<=str.length();i+=2)  
            str.insert(i,"#");  
        maxlen = 0;  
        for(pos = (str.length()-1)/2; pos >=0 ; pos--)  
        {  
            l = pos - 1;  
            r = pos + 1;  
            while(l>=0&&r<str.length()&&str[l]==str[r])  
            {  
                l--;  
                r++;  
            }  
            if(r-l-1>maxlen)  
                maxlen = r-l-1;  
            if(maxlen == 2*pos+1)  
                break;  
        }  
        for(pos = (str.length()-1)/2; pos <str.length() ; pos++)  
        {  
            l = pos - 1;  
            r = pos + 1;  
            while(l>=0&&r<str.length()&&str[l]==str[r])  
            {  
                l--;  
                r++;  
            }  
            if(r-l-1>maxlen)  
                maxlen = r-l-1;  
            if(maxlen == 2*((str.length()-1)-pos)+1)  
                break;  
        }  
        cout<<(maxlen%2?maxlen/2:maxlen/2-1)<<endl;  
  
    }  
}  
#include<iostream>  
#include<cstdio>  
#include<string>  
using namespace std;  
  
int clac(char *str, int p, int len){  
    int l = p-1, r = p+1;  
    int k = 1;  
    while(l>=0&&r<len&&str[l--]==str[r++])  
        k+=2;  
    return k;  
}  
  
int init(const char *str,int len)  
{  
    char *temp = new char[len*2+2];  
    int i = 1, j = 0, tmpint;  
    temp[0] = '#';  
    while(str[j]!='\0')  
    temp[i++] = str[j++],temp[i++] = '#';  
    temp[i] = '\0';  
    int mmax = 0;  
    i = len, j = len;  
    while(i>=0&&j<len*2+1)  
    {  
        if((tmpint=clac(temp,i--,len*2+1))>mmax)  
            mmax = tmpint;  
        if(mmax==2*i+3)  
            break;  
        if((tmpint=clac(temp,j++,len*2+1))>mmax)  
            mmax = tmpint;  
        if(mmax==2*i+3)  
            break;  
    }  
    return mmax/2;  
}  
  
  
int main()  
{  
    int n;  
    cin>>n;  
    string str;  
    while(n--)  
    {  
        cin>>str;  
        cout<<init(str.c_str(),str.length())<<endl;;  
    }  
}  

依然超时- -囧

相关文章

  • 最长回文串子串 渣渣版

    依然超时- -囧

  • 最长回文子串

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

  • 字符串算法

    最长公共前缀 最长回文串 最长回文子序列 最长公共子串 反转单词顺序列 反转字符串 字符串转数字 IP-int互转

  • Manacher算法

    最长回文子串问题# 给定一个字符串,找出最长的回文子串,如"waabwswbfd",则最长子串为bwsb. 中心试...

  • 最长回文子序列

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

  • 打卡-最长回文子串

    最长回文子串(中等)

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

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

  • 最长回文子串问题—Manacher算法

    最长回文串问题是一个经典的算法题。 0. 问题定义 最长回文子串问题:给定一个字符串,求它的最长回文子串长度。如果...

  • Manacher's Algorithm算法分析Java

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

  • LeetCode 第647题:回文子串

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

网友评论

      本文标题:最长回文串子串 渣渣版

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