BZOJ2803[Poi2012]Prefixuffix——hash

BZOJ2803[Poi2012]Prefixuffix——hash

题目描述

对于两个串S1、S2,如果能够将S1的一个后缀移动到开头后变成S2,就称S1和S2循环相同。例如串ababba和串abbaab是循环相同的。
给出一个长度为n的串S,求满足下面条件的最大的L:
1. L<=n/2
2. S的L前缀和S的L后缀是循环相同的。

输入

第一行一个正整数n (n<=1,000,000)。第二行n个小写英文字母,表示串S。

输出

一个整数,表示最大的L。

样例输入

15
ababbabababbaab

样例输出

6
 
假设两个串是循环同构的,那么这两个串可以表示成x+y和y+x的形式(其中x,y为两个字符串)
设f[i]表示前后都去掉i个字符后能匹配的最长前后缀长度,即y的最长长度。
手画一下能够发现对于位于左一半的i和i+1,f[i]<=f[i+1]+2。如果大于了就说明f[i+1]还能更大。
那么就可以从中间向开头转移f[i],最后求出i+f[i]的最大值即可。这道题卡自然溢出。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll h[1000010];
ll g[1000010];
ll base1[1000010];
ll base2[1000010];
char ch[1000010];
int mod=1e9+7;
int n;
int f[1000010];
int ans=0;
bool check(int x,int y,int l)
{
    ll s1,s2,t1,t2;
    s1=((h[x+l-1]-h[x-1]*base1[l])%mod+mod)%mod;
    s2=((g[x+l-1]-g[x-1]*base2[l])%mod+mod)%mod;
    t1=((h[y+l-1]-h[y-1]*base1[l])%mod+mod)%mod;
    t2=((g[y+l-1]-g[y-1]*base2[l])%mod+mod)%mod;
    if(s1==t1&&s2==t2)
    {
        return true;
    }
    return false;
}
int main()
{
    scanf("%d",&n);
    scanf("%s",ch+1);
    base1[0]=1;
    base2[0]=1;
    for(int i=1;i<=n;i++)
    {
        base1[i]=base1[i-1]*233%mod;
        base2[i]=base2[i-1]*2333%mod;
        h[i]=(h[i-1]*233+(ch[i]-96))%mod;
        g[i]=(g[i-1]*2333+(ch[i]-96))%mod;
    }
    for(int i=n/2;i>=1;i--)
    {
        f[i]=min(f[i+1]+2,(n-2*i)/2);
        while(f[i]&&(!check(i+1,n-f[i]+1-i,f[i])))
        {
            f[i]--;
        }
    }
    for(int i=1;i<=n/2;i++)
    {
        if(!check(1,n-i+1,i))
        {
            continue;
        }
        ans=max(ans,f[i]+i);
    }
    printf("%d",ans);
}

转载于:https://www.cnblogs.com/Khada-Jhin/p/9637166.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101431.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 固态硬盘开盘数据恢复的方法是_硬盘数据恢复原理

    固态硬盘开盘数据恢复的方法是_硬盘数据恢复原理在电脑的使用中有时因为一些不当的操作会导致固态硬盘损坏,有的网友就在现实中遇到了这种情况,咨询小编固态硬盘开盘数据恢复的方法,下面小编就将怎么恢复固态硬盘数据教给大家。更多一键重装系统的方法在这里工具/原料系统版本:win10教育版品牌型号:华为MateBookXPro方法一、固态硬盘开盘数据恢复的方法1、怎么恢复固态硬盘数据呢,首先可以查看回收站,如果被删除的数据还在回收站里点击还原即可。方法二、固态硬盘开盘数据恢复的方法1、下载安装嗨格式数据恢复大师,在首界面选择恢复模式和文件存储位置,点击扫描,

  • 关于System.gc()

    关于System.gc()

  • Fiddler抓取视频数据「建议收藏」

    准备工作:(1)、手机(安卓、ios都可以)/安卓模拟器,今天主要以安卓模拟器为主,操作过程一致。(2)、抓包工具:Fiddel下载地址:(https://www.telerik.com/download/fiddler)(3)、编程工具:pycharm(4)、安卓模拟器上安装抖音(逍遥安装模拟器)一、fiddler配置在tools中的options中,按照图中勾选后点击Actio…

  • macbook用什么记笔记_macbook怎么查看文件

    macbook用什么记笔记_macbook怎么查看文件朋友发过来一个,ziw文件,我Mac端下载了为知笔记Mac客户端,还是打不开,导入文件后只有文件标题没有文件内容解决方法:把.ziw文件后缀改成,.zip文件解压,zip文件打开HTML文件就可以正常浏览了…

    2022年10月12日
  • Windows 10版本business_editions和consumer_editions的区别?「建议收藏」

    Windows 10版本business_editions和consumer_editions的区别?「建议收藏」Windows10版本business_editions和consumer_editions的区别?【答1】二者都内置专业版,不同之处在于:consumer_editions版本包含:Home(家庭版);Education(教育版);Professional(专业版);business_editions版本包含:Education(教育版);Enterprise(企业版);Pro…

    2022年10月28日
  • linux下载安装yum(ubuntu安装yum工具)

    自动搜索最快镜像插件:yuminstallyum-fastestmirror安装yum图形窗口插件:yuminstallyumex1、安装yuminstall全部安装yuminstallpackage1安装指定的安装包package1yumgroupinsallgroup1安装程序组group12、更新和升级yumupdate全部更新yumupdatepackage1更新指定程序包package1yumcheck-update

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号