首页 > 其他分享 >字符串

字符串

时间：2023-08-03 15:13:01浏览次数：37  
标签：ch int char maxn 字符串 include 节点

复健\(Day9\)

字符串相关算法

\(1.\)最小表示法

最小表示法就是找出字符串\(s\)的循环同构串中字典序最小的那一个

时间复杂度为\(O(n)\)

char s[maxn];
int n;

int get_min(char *s)
{
	n=strlen(s+1);
	for(int i=1;i<=n;i++) s[n+i]=s[i];
	int i=1,j=2,k=0;
	while(i<=n&&j<=n)
	{
		for(k=0;k<n&&s[i+k]==s[j+k];k++);
		s[i+k]>s[j+k]?i=i+k+1:j=j+k+1;
		if(i==j) j++;//若跳转后两个指针相同，则j++，保证比较的两个字符串不同
	}
	return min(i,j);
}

模板

https://www.luogu.com.cn/problem/P1368

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 600010
using namespace std;

int s[maxn];
int n;

int get_min()
{
	for(int i=1;i<=n;i++) s[i+n]=s[i];
	int i=1,j=2,k=0;
	while(i<=n&&j<=n)
	{
		for(k=0;k<n&&s[i+k]==s[j+k];k++);
		s[i+k]>s[j+k]?i=i+k+1:j=j+k+1;
		if(i==j) j++;
	}
	return min(i,j);
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	int start=get_min();
	for(int i=start;i<=start+n-1;i++) printf("%d ",s[i]);
	return 0;
}

\(2.\)字符串哈希

把不同的字符串映射成不同的整数

对于一个长度为\(n\)的字符串\(s\)，这样定义\(Hash\)函数：\(h(s)=\sum_{i=1} ^{n} s[i]\times p^{n-i} (modM)\)

如\(abc\)哈希值为\(a\times p^2+b\times p+c\)

其中，\(p\)为一个质数，通常取其为\(131\)或者\(13331\)，\(M\)通常取大整数\(2^{64}\)，把哈希函数值\(h\)定义为\(NULL\)，超过则自动溢出，等价于取模

typedef unsigned long long ULL
const int P=131;

ULL p[maxn],h[maxn];

void init()//预处理hash函数的前缀和
{
	p[0]=1,h[0]=0;
	for(int i=1;i<=n;i++)
	{
		p[i]=p[i-1]*P;;
		h[i]=h[i-1]*P+s[i];
	}
}

ULL get(int l,int r)//计算 s[l~r]的hash值
{
	return h[r]-h[l-1]*p[r-l+1];
}

bool substr(int l1,int r1,int l2,int r2)//判断两子串是否相等
{
	return get(l1,r1)==get(l2,r2);
}

模板

https://www.luogu.com.cn/problem/P3370

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#define maxn 10010
#define N 1500
#define ULL unsigned long long
using namespace std;

const int P=131;

ULL p[maxn],h[maxn];
set<ULL> S;

void init(char *s)
{
	p[0]=1,h[0]=0;
	for(int i=1;i<=N;i++)
	{
		p[i]=p[i-1]*P;
		h[i]=h[i-1]*P+s[i];
	}
}

ULL get(int l,int r)
{
	return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char s[N];
		cin>>s;
		init(s+1);
		int len=strlen(s+1);
		S.insert(get(1,len));
	}
	printf("%d\n",S.size());
	return 0;
}

\(3.KMP\)算法

给定一个模式串\(P\)和一个主串\(S\)，求模式串\(P\)再主串\(S\)中出现的位置（字符串下标均从\(1\)开始）

\(next[i]\)表示模式串\(P[1,i]\)中相等前后缀的最长长度

使用双指针计算\(ne\)数组

ne[1]=0;
for(int i=2,=0;i<=n;i++)
{
	while(j&&P[i]!=P[j+1]) j=ne[j];//若P[i]!=P[j+1]，让j回跳到能匹配的位置
	if(P[i]==P[j+1]) j++;//指向匹配前缀的末尾
	ne[i]=j;
}

模式串与主串匹配

for(int i=1,j=0;i<=m;i++)
{
	while(j&&S[i]!=P[j+1]) j=ne[j];
	if(S[i]==P[j+1]) j++;
	if(j==n) printf("%d\n",i-n+1);//输出匹配开始的位置
}

模板

https://www.luogu.com.cn/problem/P3375

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 1000010
using namespace std;

int ne[maxn];
char S[maxn],P[maxn];

int main()
{
	cin>>(S+1);
	cin>>(P+1);
	int m=strlen(S+1);
	int n=strlen(P+1);
	ne[1]=0;
	for(int i=2,j=0;i<=n;i++)
	{
		while(j&&P[i]!=P[j+1]) j=ne[j];
		if(P[i]==P[j+1]) j++;
		ne[i]=j;
	}
	for(int i=1,j=0;i<=m;i++)
	{
		while(j&&S[i]!=P[j+1]) j=ne[j];
		if(S[i]==P[j+1]) j++;
		if(j==n) printf("%d\n",i-n+1);
	}
	for(int i=1;i<=n;i++) printf("%d ",ne[i]);
	return 0;
}

\(4.\)扩展\(KMP\)算法(\(Z\)函数)

\(Z\)函数：对于一个长度为\(n\) 的字符串\(S\)，\(z[i]\)表示\(S\)与其后缀\(S[i,n]\)的最长公共前缀\((LCP)\)的长度

\(Z-box:\)对于\(i\)，我们称区间\([i,i+z[i]-1]\)是\(i\)的匹配串，也可以叫\(Z-box\)

void get_z(char *s,int n)//s与s的每一个后缀的LCP的长度数组z
{
	z[1]=n;
	for(int i=2,l,r=0;i<=n;i++)//维护盒子s[l~r],s[l~r]=s[1~r-l+1]
	{
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);//若i在盒子内，则s[i~r]=s[i-l+1~r-l+1]
		while(s[1+z[i]]==s[i+z[i]]) z[i]++;//这是(z[i-l+1]>=r-i+1之后)或者(i>r即在盒外)的暴力枚举
		if(i+z[i]-1>r) l=i,r=i+z[i]-1;//求出z[i]后，如果i+z[i]-1>r,则更新盒子l=i,r=i+z[i]-1
	}
}

void get_p(char *s,int n,char *t,int m)//s与t的每一个后缀的LCP的长度数组
{
	for(int i=1,l,r=0;i<=m;i++)
	{
		if(i<=r) p[i]=min(z[i-l+1],r-i+1);
		while(1+p[i]<=n&&i+p[i]<=m&&s[1+p[i]]==t[i+p[i]]) p[i]++;
		if(i+p[i]-1>r) l=i,r=i+p[i]-1;
	}
}

模板

https://www.luogu.com.cn/problem/P5410

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=2e7+5;

int z[maxn],p[maxn];
char s[maxn],t[maxn];

long long get_ans(int *s,int n)
{
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		ans^=1LL*i*(s[i]+1);
	}
	return ans;
}

void get_z(char *s,int n)
{
	z[1]=n;
	for(int i=2,l,r=0;i<=n;i++)
	{
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);
		while(s[1+z[i]]==s[i+z[i]]) z[i]++;
		if(i+z[i]-1>r) l=i,r=i+z[i]-1;
	}
}

void get_p(char *s,int n,char *t,int m)
{
	for(int i=1,l,r=0;i<=m;i++)
	{
		if(i<=r) p[i]=min(z[i-l+1],r-i+1);
		while(1+p[i]<=n&&i+p[i]<=m&&s[1+p[i]]==t[i+p[i]]) p[i]++;
		if(i+p[i]-1>r) l=i,r=i+p[i]-1;
	}
}

int main()
{
	cin>>(t+1);
	cin>>(s+1);
	int n=strlen(s+1);
	int m=strlen(t+1);
	get_z(s,n);//注意这里是s
	get_p(s,n,t,m);//注意这里是s,t
	printf("%lld\n",get_ans(z,n));
	printf("%lld\n",get_ans(p,m));
}

\(5.\)\(Manacher\)（马拉车）

可以在\(O(n)\)时间内求出一个字符串中的最长回文串

首先要改造字符串：在字符之间和串两端插入\(\#\)，改造后，都变成奇回文串

scanf("%s",a+1);
int n=strlen(a+1),k=0;
s[0]='$',s[++k]='#';//s[0]='$'，是哨兵（边界）
for(int i=1;i<=n;i++) s[++k]=a[i],s[++k]='#';
n=k;

回文半径\(d[i]\)：以\(i\)为中心的最长回文串的长度的一半

加速盒子\([l,r]\)(与扩展\(KMP\)算法中的盒子是一样的)：算法过程中我们要维护右端点最靠右的最长回文串，而利用盒子就可以借助之前的状态来加速计算新的状态

void get_d(char *s,int n)
{
	d[1]=1;
	for(int i=2,l,r=0;i<=n;i++)
	{
		if(i<=r) d[i]=min(d[r-i+l],r-i+1);
		while(s[i-d[i]]==s[i+d[i]]) d[i]++;
		if(i+d[i]-1>r) l=i-d[i]+1,r=i+d[i]-1;
	}
}

原串的最长回文串就是新船的最大半径\(-1\)

模板

https://www.luogu.com.cn/problem/P3805

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=3e7;

char a[maxn],s[maxn];
int d[maxn];

void get_d(char *s,int n)
{
	d[1]=1;
	for(int i=2,l,r=0;i<=n;i++)
	{
		if(i<=r) d[i]=min(d[r-i+l],r-i+1);
		while(s[i+d[i]]==s[i-d[i]]) d[i]++;
		if(i+d[i]-1>r) l=i-d[i]+1,r=i+d[i]-1;
	}
}

int main()
{
	cin>>(a+1);
	int n=strlen(a+1);
	int k=0;
	s[0]='$',s[++k]='#';
	for(int i=1;i<=n;i++) s[++k]=a[i],s[++k]='#';
	n=k;
	get_d(s,n);
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,d[i]);
	printf("%d\n",ans-1);
	return 0;
}

\(6.\)字典树\((Trie)\)

\(Trie\)维护字符串的集合，支持两种操作：插入和查询

\(ch[p][i]\)表示节点\(p\)沿着边\(i\)(\(i\)是字母映射后的值)走到的节点编号

在单词结束点记录插入次数

void insert(char *s)
{
	int p=0;
	for(int i=0;s[i];i++)
	{
		int j=s[i]-'a';
		if(!ch[p][i]) ch[p][i]=++idx;//如果没有子结点，创建子结点
		p=ch[p][j];
	}
	cnt[p]++;//插入次数
}

int query(char *s)
{
	int p=0;
	for(int i=0;s[i];i++)
	{
		int j=s[i]-'a';
		if(!ch[p][j]) return 0;
		p=ch[p][j];
	}
	return cnt[p];
}

\(7.\)最大异或对\((01Trie)\)

给定\(N\)个整数\(a_1,a_2,\cdots,a_n\)，任选两个数进行异或运算，求得到的结果最大是多少

\(N\)个整数用二进制表示，所以我们的\(Trie\)数位一个二叉树，深度为\(31\)层

const int maxn=100010;
int n,a[maxn];
int ch[maxn*31][2],idx;

void insert(int x)
{
	int p=0;
	for(int i=30;i>=0;i--)
	{
		int j=x>>i&1;
		if(!ch[p][j]) ch[p][j]=++idx;
		p=ch[p][j];
	}
}

int query(int x)
{
	int p=0,res=0;
	for(int i=30;i>=0;i--)
	{
		int j=x>>i&1;//取出第i位
		if(ch[p][!j])//可以找到与之相反的数
		{
			res+=1<<i;
			p=ch[p][!j];
		}
		else p=ch[p][j];
	}
	return res;
}

\(8.AC\)自动机

是一个多模式匹配算法：给定\(n\)个模式串和一个主串，查找有多少个模式串在主串中出现过

\(1.\)首先，我们构造\(Trie\)树：用一个节点表示一个从根到当前节点的字符串，例如：节点\(5\)表示字符串\(she\)

如果节点是个模式串，则需打个标记\(cnt[i]=1\)

\(2.\)然后，我们构造\(AC\)自动机：在\(Trie\)上构建两类边：回跳边和转移边

\(ne[v]\)存节点\(v\)的回跳边的终点

回跳边指向父节点的回跳边所指节点的儿子，\((v,u,ne[v],ne[u])\)构成四边形

回跳边所指节点一定是当前节点的最长后缀（如果这里失配，那么我们转移到回跳边去继续匹配）

\(ch[u][i]\)存节点\(u\)的树边的终点，也存节点\(u\)的转移边的终点

转移边指向当前节点的回跳边所指节点的儿子，\((u,ne[u],ch[][])\)构成三角形

转移边所指节点一定是当前节点的最短路（就是说从当前节点到\(i\)的最短路，不必再回到前面的祖先节点去，节约了时间）

void build()//建AC自动机
{
	queue<int>	q;
	for(int i=0;i<26;i++)
		if(ch[0][i]) q.push(ch[0][i]);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			int v=ch[u][i];
			if(v) ne[v]=ch[ne[u]][i],q.push(v);
			else ch[u][i]=ch[ne[u]][i];//若儿子不存在，则父节点自建转移边
		}
	}
}

\(3.\)扫描主串匹配

int query(char *s)
{
	int ans=0;
	for(int k=0,i=0;s[k];k++)
	{
		i=ch[i][s[k]-'a'];//沿树边或者转移边走，保证不回退
		for(int j=i;j&&~cnt[j];j=ne[j])//沿回跳边搜索模式串
		{
			ans+=cnt[j],cnt[j]=-1;//这样的话，就是只累计不重复的可匹配的字符串个数，如果出现一次就累计一次，就去掉									  //cnt=-1和循环里的~cnt的条件
		}
	}
	return ans;
}

模板

https://www.luogu.com.cn/problem/P3808

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define maxn 1000010
using namespace std;

int ch[maxn][26],cnt[maxn],idx;
int ne[maxn];
char s[maxn];

void insert(char *s)
{
	int p=0;
	for(int i=0;s[i];i++)
	{
		int j=s[i]-'a';
		if(!ch[p][j]) ch[p][j]=++idx;
		p=ch[p][j];
	}
	cnt[p]++;
}

void build()
{
	queue<int> q;
	for(int i=0;i<26;i++) if(ch[0][i]) q.push(ch[0][i]);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			int v=ch[u][i];
			if(v) ne[v]=ch[ne[u]][i],q.push(v);
			else ch[u][i]=ch[ne[u]][i];
		}
	}
}
int query(char *s)
{
	int ans=0;
	for(int k=0,i=0;s[k];k++)
	{
		i=ch[i][s[k]-'a'];
		for(int j=i;j&&~cnt[j];j=ne[j])
		{
			ans+=cnt[j];
			cnt[j]=-1;
		}
	}
	return ans;
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		insert(s);
	}
	build();
	cin>>s;
	printf("%d\n",query(s));
	return 0;
}

之后有空再学习：

\(9.\)后缀自动机\((SAM)\)

有链接边和转移边

\(ch[x][c]\)存节点\(x\)的转移边的终点，\(fa[x]\)存节点\(x\)的链接边的终点，\(len[x]\)存节点\(x\)的最长串的长度

\(10.\)后缀数组\((SA)\)

\(sa[i]\)表示排名为\(i\)的后缀编号，\(rk[i]\)表示后缀\(i\)的排名，\(height[i]=lap(sa[i],sa[i-1])\)表示第\(i\)名后缀与第\(i-1\)名后缀的最长公共前缀的长度（高度数组表示两个后缀的相似度，排序相邻的两个后缀相似度最高）

void get_sa()//n为后缀个数，m为桶的个数，桶数组x,辅助数组y,计数数组c
{
	int i,j,k;
	//按第一个字母排序
	for(i=1;i<=n;i++) c[x[i]=s[i]]++;//按第一个字母边桶号并累计
	for(i=1;i<=m;i++) c[i]+=c[i-1];
	for(i=n;i;i--) sa[c[x[i]]--]=i;//后缀i的排序是i所在的桶号的剩余累计值
	for(k=1;k<=n;k++)
	{
		//按第二关键字排序
		memset(c,0,sizeof(c);
		for(i=1;i<=n;i++) y[i]=sa[i];
		for(i=1;i<=n;i++) c[x[y[i]+k]]++;
		for(i=1;i<=m;i++) c[i]+=c[i-1];
		for(i=n;i;i--) sa[c[x[y[i]+k]]--]=y[i];//后缀y[i]的排序是第二关键字所在的桶号的剩余累计值
	}
}

标签：ch,int,char,maxn,字符串,include,节点
From： https://www.cnblogs.com/iwillenter-top1/p/17603399.html

相关文章

  • 使用正则表达式 移除 HTML 标签后得到字符串
    需求分析后台返回的数据是这样式的需要讲html标签替换high_light_text:"<spanstyle='color:red'>OPPO</span><spanstyle='color:red'>OPPO</span>白色01"使用正则表达式functionstripHTMLTags(htmlString){returnhtmlString.repl......
  • [代码随想录]Day07-字符串 part01
    题目：344.反转字符串思路：每次把最前面和最后面的交换位置即可strings库里没有反转的方法——这个反转是之后几个题的一个基础代码：双指针调换位置funcreverseString(s[]byte){l,r:=0,len(s)-1//最前面的元素，最后面的元素forl<r{s[l],s[......
  • Python教程(6)——Python变量的基础类型。|整数类型|浮点数类型|字符串类型|布尔类型|
    学习编程语言，不得不忽视变量这个概念。Python中的变量是用于存储数据的名称，你可以将值赋给变量，并在程序的其他地方使用该变量来引用该值。变量在程序中起到存储和操作数据的作用。如果学过C/C++语言的同学，定义了变量后，需要加个类型的限制，比如intage=28doublemoney=10.2......
  • java 十六进制字符串转换为有符号整数
    StringhexString="FEF7";//十六进制字符串intintValue=Integer.parseInt(hexString,16);//将十六进制字符串转换为整数shortsignedValue=(short)intValue;//转换为短整型（16位有符号整数）intintValue=(bytes[1]&0xFF)<<8|(bytes[0]&0xFF);//合并......
  • 字符串转化为整数的C库函数
    #include<stdio.h>#include<stdlib.h>intmain(void){charstr[10]="12345";charstr1[10]="hello";intval;val=atoi(str);printf("val=%d,str=%s\r\n",val,str);val=atoi(s......
  • 初学C语言day08--字符串
    字符串字符：字符是在计算机中以整数形式存储的，在需要显示成字符时会根据ASCII表中对应的关系，来显示对应的符号或图案'\0'0空字符'0'48'A'65'a'97串：是一种数据结构，是由一组连续的若干个类型相同的数据组成，末尾有一个结束标志对于这种数据结构的处理......
  • 实验六 字符串的基本操作
    实验六字符串的基本操作一、实验目的1、培养分析问题并对进行建模的能力。2、熟练运用字符串基本功能解决实际问题。二、实验内容1、获取字符串中汉字的个数，如：“我的English学的不好”汉子个数是6个。2、去掉字符串数组中每个字符串的空格，如：“todayisagoodday”结果......
  • 实验七 字符串的内建函数
    实验七字符串的内建函数一、实验目的1、培养分析问题并对进行建模的能力。2、熟练运用字符串内键函数解决实际问题。二、实验内容1、将字母全部转换为大写或小写，如：”ILovePython”转化结果：“ilovepython”或者“ILOVEPYTHON”2、判断用户名是否合法，从键盘上输入一个用户......
  • 逆向——字符与字符串，中文字符GB2312编码由来
    字符与字符串在之前的课程中我们了解到变量的定义决定两个事情，第一是决定存储的数据宽度，第二是决定了存储的数据格式，那么我们来看下下面的代码：inta=123;//变量x，数据宽度为4个字节，里面存储的是补码（在计算机系统中，数值一律用补码来存储）intfloatb=123.4F;//IEEE编码（浮点）......
  • golang json字符串转结构体
    1、不知道结构体类型的情况下funcJsonStringToMap(jsonStrstring)(map[string]interface{},error){//未知值类型m:=make(map[string]interface{})err:=json.Unmarshal([]byte(jsonStr),&m)iferr!=nil{fmt.Printf("Unmarshalwither......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99