首页 > 其他分享 >后缀自动机

后缀自动机

时间:2023-04-01 12:11:49浏览次数:30  
标签:cur 后缀 father len son int nq 自动机

后缀自动机是通过一个DAG图来存储的,使空间更小,后缀自动机中最关键的一项技术叫做后缀链。

1.建立SAM

void insert(int c){
	newNode(t[last].len+1);
	int p=last,cur=sz;
	while(p!=-1&&!t[p].son[c])t[p].son[c]=cur,p=t[p].father;
	if(p==-1)t[cur].father=0;
	else{
		int q=t[p].son[c];
		if(t[q].len==t[p].len+1)t[cur].father=q;
		else{
			newNode(t[p].len+1);
			int nq=sz;
			memcpy(t[nq].son,t[q].son,sizeof(t[q].son));
			t[nq].father=t[q].father;
			t[cur].father=t[q].father=nq;
			while(p>=0&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].father;
		}
	}
	last=cur;
}

  

2.例题:HDU4622

这道题求的是区间内不同的子串个数,可以使用dp的思路,递推求解所有区间的答案

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+255;
int sz,last,ans[N][N];
char s[N];
struct node{
	int son[26],father,len;
}t[N<<1];
void newNode(int length){
	t[++sz].len=length;
	t[sz].father=-1;
	memset(t[sz].son,0,sizeof(t[sz].son));
}
void init(){
	sz=-1;last=0;
	newNode(0);
}
void insert(int c){
	newNode(t[last].len+1);
	int p=last,cur=sz;
	while(p!=-1&&!t[p].son[c])t[p].son[c]=cur,p=t[p].father;
	if(p==-1)t[cur].father=0;
	else{
		int q=t[p].son[c];
		if(t[q].len==t[p].len+1)t[cur].father=q;
		else{
			newNode(t[p].len+1);
			int nq=sz;
			memcpy(t[nq].son,t[q].son,sizeof(t[q].son));
			t[nq].father=t[q].father;
			t[cur].father=t[q].father=nq;
			while(p>=0&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].father;
		}
	}
	last=cur;
}
int main(){
	int T;cin>>T;
	while(T--){
		cin>>s;
		int n=strlen(s);
		for(int i=0;i<n;i++){
			init();
			for(int j=i;j<n;j++){
				insert(s[j]-'a');
				ans[i][j]=ans[i][j-1]+t[last].len-t[t[last].father].len;
			}
		}
		int Q,l,r;cin>>Q;
		while(Q--){
			cin>>l>>r;
			cout<<ans[--l][--r]<<'\n';
		}
	}
	return 0;
} 

  

标签:cur,后缀,father,len,son,int,nq,自动机
From: https://www.cnblogs.com/zhanghx-blogs/p/17278387.html

相关文章

  • 中缀逻辑表达式转后缀逻辑表达式
    #include<bits/stdc++.h>usingnamespacestd;/*中缀逻辑表达式转后缀逻辑表达式测试用例:0&(0|1|0)答案:001|0|&*/unordered_map<char,int>h{{'|',1},{'&',2}};strings;stringt;stack<char>stk;intmain(){cin......
  • 中缀表达式转后缀表达式
    中缀表达式转后缀表达式一、中缀表达式和后缀表达式的区别中缀表达式就是我们通常认知中的表达式,比如\[1+((2+3)*4)-5\]这样的表达式虽然容易被人所理解,但是不容易被机器所识别,为此推出了后缀表达式。后缀表达式又被叫做逆波兰表达式,逆波兰表达式不需要被括号所识别,且容易被机......
  • U兑换TRX的自动机器人怎么开发?一篇文章教你部署
    TRX兑币机器人现在在telegram电报上非常流行了,很多用户都开始接受了这样的兑币方式。相对于使用币安或者火币来说,用户通过机器人兑换TRX更加方便快捷,不需要充币提币等......
  • AC自动机相关模板
    P5357#include<bits/stdc++.h>#defineintlonglong#defineN200005usingnamespacestd;intn,cnt[N]={0};strings[N],t;map<string,int>apr;string......
  • 学习笔记:AC自动机
    AC自动机是一种多模匹配算法,AC自动机常常用于多模式串,单文本串的匹配算法。在此之前,你应当学会KMP&Trie。我们先给一组例子:abcdbcdcddacad这是这组例子建成的......
  • AC自动机
    用于解决多模式串匹配相关问题。实际上就是KMP在多串的扩展。首先建出字符串的trie树,然后AC自动机只是在trie树上加了一些边。只需要记住:儿子的fail就是fail......
  • 后缀表达式的值
    【例1-2】后缀表达式的值时间限制:10ms      内存限制:65536KB提交数:850   通过数:119 【题目描述】从键盘读入一个后缀表达式(字符串),只含有0-9组成的......
  • Windows下批量修改文件后缀名
    将要修改的同一后缀名的文件放在一个文件夹下,新建文本文件,写入:ren*.旧后缀名*.新后缀名,例:ren*.webp*.jpg//将webp格式文件修改为jpg格式。然后将文本文件另存为ba......
  • 浅谈后缀自动机
    后缀自动机自动机首先什么是自动机我们大多用的是\(DFA\),也就是有限状态自动机整个自动机是由一些边和点组成的,边上的权为字符简单理解就是输入一个字符串如果是我......
  • 中缀表达式转后缀表达式
      代码实现importjava.util.ArrayList;importjava.util.List;importjava.util.Stack;publicclasstext1{publicstaticvoidmain(String[]args){......