首页 > 其他分享 >[HAOI2016] 找相同字符

[HAOI2016] 找相同字符

时间:2024-01-30 17:55:08浏览次数:32  
标签:字符 相同 int long t1 HAOI2016 500005

  • 容斥原理
  • 将两个字符串拼接起来(中间用‘#’分隔开),再减去它们内部的贡献
  • height数组支持的最长公共前缀:不仅是长度,也是子串的个数
  • 返回值开long long
  • 核心代码与[AHOI2013] 差异 一致
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int sa[500005];
int rk[20][500005],w,n,p[25],r[500005];
long long h[500005];
stack<int>s1;
stack<int>s2; 
struct t1
{
	char c;
	int id;
}t[500005];
bool cmp1(t1 a,t1 b)
{
	return a.c<b.c;
}
bool cmp2(int a,int b)
{
	if(rk[w-1][a]!=rk[w-1][b])
	{
		return rk[w-1][a]<rk[w-1][b];
	}
	return rk[w-1][min(a+p[w-1],n+1)]<rk[w-1][min(b+p[w-1],n+1)];
}
long long calc(string s)
{
	memset(rk,0,sizeof(rk));
	n=s.size();
	for(int i=1;i<=n;i++)
	{
		t[i].c=s[i-1];
		t[i].id=i;
		sa[i]=i;
	}
	sort(t+1,t+n+1,cmp1);
	int cnt=0;
	t[0].c=' ';
	for(int i=1;i<=n;i++)
	{
		if(t[i].c!=t[i-1].c)
		{
			cnt++;
		}
		rk[0][t[i].id]=cnt;
	}
	for(int i=1;i<=19;i++)
	{
		w=i;
		sort(sa+1,sa+n+1,cmp2);
		cnt=0;
		for(int j=1;j<=n;j++)
		{
			if(rk[w-1][sa[j]]!=rk[w-1][sa[j-1]]||rk[w-1][min(sa[j]+p[w-1],n+1)]!=rk[w-1][min(sa[j-1]+p[w-1],n+1)])
			{
				cnt++;
			}
			rk[w][sa[j]]=cnt;
		}
	}
	for(int i=1;i<=n;i++)
	{
		r[i]=rk[19][i];
	}
	int k=0;
	for(int i=1;i<=n;i++)
	{
		if(r[i]==1)
		{
			h[1]=0;
			k=0;
			continue;
		}
		while(i+k-1<n&&sa[r[i]-1]+k-1<n&&s[i+k-1]==s[sa[r[i]-1]+k-1])
		{
			k++;
		}
		h[r[i]]=k;
		if(k)
		{
			k--;
		}
	}
	long long ans=0,cur=0;
	while(!s1.empty())
	{
		s1.pop();
		s2.pop();
	}
	for(int i=1;i<=n;i++)
	{
		while(!s1.empty()&&h[i]<h[s1.top()])
		{
			cur=cur-h[s1.top()]*s2.top();
			s1.pop();
			s2.pop();
		}
		if(s2.empty())
		{
			s2.push(i-1);
		}
		else
		{
			s2.push(i-1-(s1.top()-1));
		}
		s1.push(i);
		cur=cur+h[i]*s2.top();
		ans=ans+cur;
	}
	return ans;
}
int main()
{
	p[0]=1;
	for(int i=1;i<=20;i++)
	{
		p[i]=p[i-1]*2;
	}
	string s1,s2;
	cin>>s1>>s2;
	cout<<calc(s1+'#'+s2)-calc(s1)-calc(s2)<<endl;
	return 0;
}

标签:字符,相同,int,long,t1,HAOI2016,500005
From: https://www.cnblogs.com/watersail/p/17997668

相关文章

  • 151. 反转字符串中的单词(中)
    目录题目法一、双指针法二、字符串常用操作题目给你一个字符串s,请你反转字符串中单词的顺序。单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意:输入字符串s中可能会......
  • SQLServer 字符集的学习与验证
    SQLServer字符集的学习与验证背景因为开发JDBCforSQLServer的一群大佬自作主张的进行了AsUnicode的默认参数值设置.导致数据库采用了varchar的列到出现了隐式转换,有非常大的性能损耗.单独改过来又担心出现乱码的问题(毕竟这个比较2的选项就是为了解决乱码问题)没办......
  • C# - 使用 Spire.PDF 将HTML网页、网页内容、HTML字符串转换为PDF
    将HTML转换为PDF可实现格式保留、可靠打印、文档归档等多种用途,满足不同领域和情境下的需求。本文将通过以下两个示例,演示如何使用第三方库Spire.PDFfor.NET和QT插件在C#中将Html网页(URL)或HTML字符串转为PDF文件。 HTML转PDF所需工具:1.Spire.PDFfor.NET首先需要安装S......
  • C# - 将HTML网页、HTML字符串转换为PDF
    将HTML转换为PDF可实现格式保留、可靠打印、文档归档等多种用途,满足不同领域和情境下的需求。本文将通过以下两个示例,演示如何使用第三方库Spire.PDFfor.NET和QT插件在C#中将Html网页(URL)或HTML字符串转为PDF文件。 HTML转PDF所需工具:1.Spire.PDFfor.NET首先需要安装Sp......
  • pdf转base64字符串及base64字符串反转pdf
    pdf转base64//转base64publicStringfileToBase64(){//StringimgFilePath="C:\\Users\\zlf\\Desktop\\pdf\\042002200211_87910810.pdf";StringimgFilePath="C:\\Users\\zlf\\Desktop\\pdf\\【高德打车-38.65元......
  • uniapp ArrayBuffer转16进度字符串 以及 十六进制转ASCII码
    1.ArrayBuffer转16进度字符串//ArrayBuffer转16进度字符串示例//ab2hex(buffer){//consthexArr=Array.prototype.map.call(//newUint8Array(buffer),//function(bit){//......
  • 字符串
    $\largeBorder:若字符串同长度的前缀和后缀完全相同,即Prefix[i]=suffix[i],称此前(后)缀为字符串的一个Border$重要性质 $\largep是S的周期\Leftrightarrow|S|-p是S的Border$$\large所以求周期等价于求Border,Border不具备二分性$$\largeS的Border的Border也是......
  • Pdfium.Net.Free 一个免费的Pdfium的 .net包装器--创建字符子集
    项目地址:Pdfium.Net:https://github.com/1000374/Pdfium.NetPdfiumViewer:https://github.com/1000374/PdfiumViewerPdfium.Net.Free一个免费的Pdfium的.net包装器--加载字体 接上篇,怎么创建字符子集呢?获取字符集内的字形符号需要引用wpf下PresentationCore.dll,根据比对传入......
  • 查询表、视图字符串字段的长度
    SELECTa.colorder字段序号,a.name字段名,b.name类型,CASEWHENCOLUMNPROPERTY(a.id,a.name,'PRECISION')=-1THEN',长度无限制'ELSE',长度限制'+CAST(COLUMNPROPERTY(a.id,......
  • C#正则提取字符串中的数字
    首先需要引入命名空间System.Text.RegularExpressions,具体实现如下所示://提取纯数字,该方式会将所有数字提取出来并拼接在一起,如:"ABC#123@AS456测试"提取出来就是123456varresult1=Regex.Replace("ABC#123@AS测试",@"[^0-9]+","");//提取多个数字,该方式会分别提取字符串中......