您现在的位置是:首页 > 正文

【HAOI2016】找相同字符

2024-02-01 04:10:29阅读 1

后缀自动机入门题

分别对两个串建后缀自动机,然后把endpos的大小算出来,最后在两个后缀自动机上一起dfs一遍并且算答案。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=5e5+10;
int n;
char s[maxn];
long long ans;
struct suda
{
	struct da{int ch[30],fa,len;}po[maxn];
	int las,tot,si[maxn],to[maxn],nt[maxn],st[maxn],topt;
	void init()
	{
		memset(po,0,sizeof po); memset(si,0,sizeof si);
		memset(to,0,sizeof to); memset(nt,0,sizeof nt);
		memset(st,0,sizeof st); las=tot=1; topt=0;
	}
	void insert(int x)
	{
		int p=las,np=las=++tot; po[np].len=po[p].len+1; si[np]=1;
		for (;p&&(!po[p].ch[x]);p=po[p].fa) po[p].ch[x]=np;
		if (!p) po[np].fa=1;
		else
		{
			int q=po[p].ch[x];
			if (po[q].len==po[p].len+1) po[np].fa=q;
			else
			{
				int nq=++tot; po[nq]=po[q];
				po[nq].len=po[p].len+1;
				po[np].fa=po[q].fa=nq;
				for (;p&&(po[p].ch[x]==q);p=po[p].fa) po[p].ch[x]=nq;
			}
		}
	}
	void add(int x,int y){to[++topt]=y; nt[topt]=st[x]; st[x]=topt;}
	void getsi(int x)
	{
		int p=st[x];
		while (p)
		{
			getsi(to[p]);
			si[x]+=si[to[p]];
			p=nt[p];
		}
	}
	void solve()
	{
		for (int i=2;i<=tot;++i) add(po[i].fa,i);
		getsi(1);
	}
}SAM[3];
void dfs(int x1,int x2)
{
	for (int i=0;i<26;++i)
	if (SAM[1].po[x1].ch[i] && SAM[2].po[x2].ch[i])
	{
/*		if (x1==1 && x2==1)
		{
			printf("%c %d %d\n",'a'+i,SAM[1].si[SAM[1].po[x1].ch[i]],SAM[2].si[SAM[2].po[x2].ch[i]]);
		}*/
		ans+=1ll*SAM[1].si[SAM[1].po[x1].ch[i]]*SAM[2].si[SAM[2].po[x2].ch[i]];
		dfs(SAM[1].po[x1].ch[i],SAM[2].po[x2].ch[i]);
	}
}
int main()
{
	for (int j=1;j<=2;++j)
	{
		scanf("%s",s+1); n=strlen(s+1); SAM[j].init();
		for (int i=1;i<=n;++i) SAM[j].insert(s[i]-'a');
		SAM[j].solve();
	}
	dfs(1,1); printf("%lld\n",ans);
return 0;
}

 

网站文章

  • SQLSERVER 查看sql执行状态,死锁等待

    SELECT [Spid] = session_Id, ecid, [Database] = DB_NAME(sp.dbid), [User] = nt_username, [Status] ...

    2024-02-01 04:10:22
  • 深入 Java 调试体系,第 4 部分: Java 调试接口(JDI)

    深入 Java 调试体系,第 4 部分: Java 调试接口(JDI)

    JDI 简介JDI(Java Debug Interface)是 JPDA 三层模块中最高层的接口,定义了调试器(Debugger)所需要的一些调试接口。基于这些接口,调试器可以及时地了解目标虚拟机的状态,例如查看目标虚拟机上有哪些类和实例等。另外,调试者还可以控制目标虚拟机的执行,例如挂起和恢复目标虚拟机上的线程,设置断点等。目前,大多数的 JDI 实现都是通过 Java 语言编

    2024-02-01 04:09:52
  • 基于javaweb+mysql的jsp+servlet个人博客系统(java+jsp+servlet+mysql) 最新发布

    基于javaweb+mysql的jsp+servlet个人博客系统(java+jsp+servlet+mysql) 最新发布

    基于javaweb+mysql的jsp+servlet个人博客系统(java+jsp+servlet+mysql)基于javaweb+mysql的JSP+Servlet个人博客系统(java+jsp+servlet+mysql)eclipse/idea/myeclipse/sts等均可配置运行。课程设计,大作业,毕业设计,项目练习,学习演示等。

    2024-02-01 04:09:44
  • 温故而知新!月薪20k+的Java面试都问些什么?BAT大厂面试总结

    温故而知新!月薪20k+的Java面试都问些什么?BAT大厂面试总结

    前言 现如今的互联网应用大都是采用 分布式系统架构 设计的,所以 消息队列 已经逐渐成为企业的应用系统 内部通信 的核心手段, 它具有 低耦合、可靠投递、广播、流量控制、最终一致性 等一系列功能。 当...

    2024-02-01 04:09:36
  • 访问差异类型的集合类--visitor模式入门

    访问差异类型的集合类--visitor模式入门

    一,问题提出访问同一类型的集合类是我们最常见的事情了,我们工作中这样的代码太常见了。1  Iterator ie  =  list.iterator();2  while (ie.hasNext()) {3     Person p  =  (Person)ie.next();4     p.doWork();5 }这种访问的特点是集合类中的对象是同一类对象Person,他们拥...

    2024-02-01 04:09:10
  • “第五空间”wp-misc-run

    “第五空间”wp-misc-run

    第一次正式比赛二血。小开心。下载下来是一个run.exe。运行一下没反应…看图表是个docx,7zip打开,果然嵌了一个docx。打开,查十六进制等等基本操作,没发现有什么东西。回去运行分离出来的ex...

    2024-02-01 04:09:02
  • Flask实现CSRF保护

    Flask实现CSRF保护

    参考官方文档 CSRF跨站请求伪造,源于WEB的隐式身份验证机制,WEB的身份验证机制虽然可以抱着一个请求时来自于某个用户的浏览器,但却无法保证该请求是用户批准发送的。 例如,用户登录受信任的网址A,在本地生成了Cookie,在Cookie没有失效的情况下去访问了危险网站B,B可能会盗用你的身份,以你的名义去发送恶意请求,邮件,盗取你的账号,设置购买商品,造成你个人隐私泄露,已经财产安...

    2024-02-01 04:08:55
  • 修改git tag的描述信息

    修改git tag的描述信息

    修改git tag的描述信息message

    2024-02-01 04:08:50
  • C语言实现反序输出、分解质因数、回文数判断、斐波那契数列、素数判断、零钱换整、求兔子总数

    C语言实现反序输出、分解质因数、回文数判断、斐波那契数列、素数判断、零钱换整、求兔子总数

    C语言实现反序输出、分解质因数、回文数判断,斐波那契数列、素数判断、零钱换整、求兔子总数

    2024-02-01 04:08:20
  • 时间旅行的Bug 奇怪的输入Bug

    时间旅行的Bug 奇怪的输入Bug

    他将这个Bug保留在应用程序中,并在用户选择时间旅行时显示一个提示信息,告诉他们实际上并没有进行真正的时间旅行,而只是在虚拟世界中进行了体验。有时候,一些奇怪的输入可能会暴露出我们程序中隐藏的问题,这...

    2024-02-01 04:08:14