竞赛讨论区 > hash暴力卡过去就行了
头像
碎梦轻尘
发布于 2019-11-23 22:54
+ 关注

hash暴力卡过去就行了

#include<iostream>
#include<cstring>
using namespace std;
typedef unsigned long long int unlarge;
const int maxn=1e5+5;
unlarge heap[maxn],p[maxn];
int x=131;
char ch[maxn];
unlarge get(int left,int right)
{
    return heap[right]-heap[left-1]*p[right-left+1];
}
void tohash(char *ch,int n)
{
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        heap[i]=heap[i-1]*x+ch[i]-'a';
        p[i]=p[i-1]*x;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>(ch+1);
    
    int end=0;
    int len=strlen(ch+1);
    tohash(ch,len);
    for(int i=len/2;i;i--)
    {
        if(get(1,i)!=get(len-i+1,len))
            continue;
        int f=0;
        for(int j=i+1;j<len-i+1;j++)
            if(get(1,i)==get(j,j+i-1))
            {
                f=1;break;
            }
        if(f)
        {
            end=i;
            break;
        }
            
    }
    for(int i=1;i<=end;i++)
        cout<<ch[i];
    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐