vim复制 debugging nhibernate sms Modernizr vue绑定class 郑州小程序公司 jq延时 mysql当前时间减一天 打印缩放怎么设置 增删改查sql语句 vue使用bootstrap python集合操作 java继承 java环境配置 java写入文件 java表达式 java最新框架 linux教学 千元以下最好的手机 tt语音官网 python爬虫代码 骰子牛牛怎么玩 asp编程 fireworks office2010免费版 砸金蛋抽奖活动 黑域使用教程 lol修改皮肤 su模型交错 vue响应式原理 视频下载高手 shell数组遍历 ucs怎么用 cdr怎么复制图形 cad标题栏 上传图片 360街机三国 pdf分割合并工具 标记宏
当前位置: 首页 > 学习教程  > 编程语言

【字符串哈希】P5546 [POI2000]公共串

2020/11/24 9:56:11 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

直接二分答案&#xff0c;然后用一个map记录一下1到n-1串长度为mid的hash值&#xff0c;再和n行一个个比较就好了 代码 #include<bits/stdc.h> using namespace std; typedef long long ll; char s[6][2005]; int sum[6][2005],n; ll jc[2005],has[6][2005]; ll base133…

 

直接二分答案,然后用一个map记录一下1到n-1串长度为mid的hash值,再和n行一个个比较就好了

 

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[6][2005];
int sum[6][2005],n;
ll jc[2005],has[6][2005];
ll base=133;
map <int,ll> G[6];
void init()
{
	jc[0]=1;
	for(int i=1;i<=2000;i++) jc[i]=jc[i-1]*base;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=strlen(s[i]+1);j++)
			has[i][j]=has[i][j-1]*base+sum[i][j];
}
ll get(int now,int l,int r)
{
	return has[now][r]-has[now][l-1]*jc[r-l+1];
}
bool check(int mid)
{
	for(int i=1;i<=n;i++) G[i].clear();
	for(int i=1;i<n;i++)
		for(int j=1;j+mid-1<=strlen(s[i]+1);j++)
		{
			ll x=get(i,j,j+mid-1);
			G[i][x]=1;
		}
	for(int j=1;j+mid-1<=strlen(s[n]+1);j++)
	{
		ll x=get(n,j,j+mid-1);
		bool flag=false;
		for(int i=1;i<n;i++)
			if(!G[i][x]) flag=true;
		if(flag==false ) return true;
	}
	return false;
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	int id,len=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s[i]+1);
		for(int j=1;j<=strlen(s[i]+1);j++)
			sum[i][j]=s[i][j]-'a'+1;
		if(strlen(s[i]+1)>len)
		{
			len=strlen(s[i]+1);
			id=i;
		}
	}
	init();
	int l=1,r=len,ans;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d",ans);
	return 0;
}

 


本文链接: http://www.dtmao.cc/news_show_400195.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?