• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 20200212 專題:后綴自動機(SAM)

    標簽: 專題  # 后綴自動機

    總覽:

    OI WiKi(詳細介紹)
    后綴自動機可視化

    概述:

    能解決的問題:

    • 檢查字符串是否出現
    • 不同子串個數
    • 所有不同子串的總長度
    • 字典序第 kk 大子串
    • 最小循環移位
    • 出現次數
    • 第一次出現的位置
    • 所有出現的位置
    • 最短的沒有出現的字符串
    • 兩個字符串的最長公共子串
    • 多個字符串間的最長公共子串
      時間和空間復雜度都是線性的!
      對于長度為nn的字符串,最多2n?12n-1個節點和3n?43n-4條邊

    維護信息:

    通常為:

    struct SAM{
    	int len,fa;
    	int nex[26];//如果不是小寫字母可用unordered_map
    }tree[2*A];
    

    lenlen為指向此節點的邊所代表的字符在數組中的位置(也是此節點代表的最長子串的長度)
    fafalinklink)為出現次數比此節點維護的出現次數多的最長后綴
    nexnex為子節點(類似AC自動機)

    性質:

    結束位置endpos:
    對于一個子串,在原字符串中出現的結束位置的集合
    如:對于ababcabcababcabcendpos("ab")={2,4,7}endpos("ab")=\{2,4,7\}

    每一個節點僅維護一類endposendpos(即endposendpos相同的子串在同一個節點中)
    則一個節點中的子串短的必為長的后綴,且子串長度必為一段連續區間
    nexnex構成有向無環圖(字符維護在邊上),fafa構成一棵樹在這里插入圖片描述
    在圖上,任意一條路徑代表的字符串為原字符串的子串
    在樹上,祖宗節點為子節點的后綴,且在原字符串中的出現次數比子節點少(即uuvv的祖宗,則endpos(v)?endpos(u)endpos(v)\subseteq endpos(u)
    所以節點uuvv所對應的字符串的最大公共后綴為lca(u,v)lca(u,v)所對應的字符串
    節點對應子串的出現次數為其所有子節點對應子串出現次數之和
    每個節點所對應的子串數量為tree[u].len-tree[tree[u].fa].len

    建立自動機:

    在線算法,將節點一個一個加入。
    步驟:
    在這里插入圖片描述
    可手推!

    模板:

    inline void build(){
    	tree[0].len=0,tree[0].fa=-1;
    	las=tot=0;
    	memset(tree[0].nex,0,sizeof(tree[0].nex));//重復使用初始化
    	return;
    }
    
    inline void add(int x){
    	int now=++tot;
    	memset(tree[now].nex,0,sizeof(tree[now].nex));//重復使用初始化
    	tree[now].len=tree[las].len+1;
    	int p=las;
    	while(p!=-1&&!tree[p].nex[x]){
    		tree[p].nex[x]=now;
    		p=tree[p].fa;
    	}
    	if(p==-1)	tree[now].fa=0;
    	else{
    		int q=tree[p].nex[x];
    		if(tree[q].len==tree[p].len+1)	tree[now].fa=q;
    		else{
    			int cur=++tot;
    			tree[cur].len=tree[p].len+1;
    			tree[cur].fa=tree[q].fa;
    			for(int i=0;i<26;i++)
    				tree[cur].nex[i]=tree[q].nex[i];
    			while(p!=-1&&tree[p].nex[x]==q){
    				tree[p].nex[x]=cur;
    				p=tree[p].fa;
    			}
    			tree[now].fa=tree[q].fa=cur;
    		}
    	}
    	las=now;
    	return;
    }
    
    signed main(){
    	build();
    	for(int i=0;i<m;i++)
    		add(a[i]-'a');
    	return 0;
    }
    

    T1 P4070 [SDOI2016]生成魔咒

    P4070 [SDOI2016]生成魔咒
    Description
    魔咒串由許多魔咒字符組成,魔咒字符可以用數字表示。例如可以將魔咒字符 1、2 拼湊起來形成一個魔咒串[1,2]。
    一個魔咒串 S 的非空字串被稱為魔咒串 S 的生成魔咒。
    例如 S=[1,2,1] 時,它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五種。S=[1,1,1] 時,它的生成魔咒有 [1]、[1,1]、[1,1,1] 三種。最初 S 為空串。共進行 n 次操作,每次操作是在 S 的結尾加入一個魔咒字符。每次操作后都需要求出,當前的魔咒串 S 共有多少種生成魔咒。

    Input
    第一行一個整數 nn
    第二行 nn 個數,第 ii 個數表示第 ii 次操作加入的魔咒字符。
    1n1000001≤n≤100000。用來表示魔咒字符的數字 xx 滿足 1x1091≤x≤10^9

    Output
    輸出 nn 行,每行一個數。第 ii 行的數表示第 ii 次操作后 S 的生成魔咒數量

    Sample Input
    7
    1 2 3 3 3 1 2

    Sample Output
    1
    3
    6
    9
    12
    17
    22

    思路:
    一句話題意:求不重復的子串數量
    加入一個字符后,增加字符為末尾字符,對應lastlast節點,增加子串數量為tree[now].len?tree[tree[now].fa].lentree[now].len-tree[tree[now].fa].len,每次累加即可

    代碼:

    #include<bits/stdc++.h>
    #include<tr1/unordered_map>
    using namespace std;
    #define in Read()
    #define int long long
    
    inline int in{
    	int s=0,f=1;char x;
    	for(x=getchar();x<'0'||x>'9';x=getchar())	if(x=='-')	f=-1;
    	for( ;x>='0'&&x<='9';x=getchar())	s=(s<<1)+(s<<3)+(x&15);
    	return f==1?s:-s;
    }
    
    const int A=1e5+5;
    int n;
    struct SAM{
    	int len,fa;
    	tr1::unordered_map <int,int> nex;
    }tree[4*A];
    int tot,last;
    int ans=0;
    
    inline void insert(int x){
    	int now=++tot;
    	tree[now].len=tree[last].len+1;
    	int p=last;
    	while(p!=-1&&!tree[p].nex.count(x)){
    		tree[p].nex[x]=now;
    		p=tree[p].fa;
    	}
    	if(p==-1)	tree[now].fa=0;
    	else{
    		int q=tree[p].nex[x];
    		if(tree[p].len+1==tree[q].len)	tree[now].fa=q;
    		else{
    			int cur=++tot;
    			tree[cur].len=tree[p].len+1;
    			tree[cur].fa=tree[q].fa;
    			tree[cur].nex=tree[q].nex;
    			while(p!=-1&&tree[p].nex[x]==q){
    				tree[p].nex[x]=cur;
    				p=tree[p].fa;
    			}
    			tree[q].fa=tree[now].fa=cur;
    		}
    	}
    	last=now;
    	ans+=tree[now].len-tree[tree[now].fa].len;
    	return;
    }
    
    inline void build(){
    	tree[0].len=0,tree[0].fa=-1;
    	last=0;
    	return;
    }
    
    signed main(){
    	n=in;
    	build();
    	while(n--){
    		int x=in;
    		insert(x);
    		printf("%lld\n",ans);
    	}
    	return 0;
    }
    

    T2 P3804 【模板】后綴自動機 (SAM)

    P3804 【模板】后綴自動機 (SAM)
    題目描述
    給定一個只包含小寫字母的字符串SS
    請你求出 SS 的所有出現次數不為 11 的子串的出現次數乘上該子串長度的最大值。

    輸入格式
    一行一個僅包含小寫字母的字符串SS

    輸出格式
    一個整數,為所求答案

    輸入輸出樣例
    輸入
    abab

    輸出
    4

    說明/提示
    對于100%00\%的數據,S<=106|S|<=10^6

    思路:
    建立后綴自動機,在fafa的樹上,葉節點對應子串的出現次數為11,拓撲排序后dpdp出所有節點的次數。一個節點對應子串的出現次數相同,對應最長子串的長度為tree[x].lentree[x].len。掃描更新答案即可。

    因為復雜度O(n)O(n),所以拓撲排序不能用sortsort,可以桶排序:

    int num[2*A],pos[2*A],cnt[2*A];
    
    inline void toopsort(){
    	for(int i=1;i<=tot;i++)	num[tree[i].len]++;
    	for(int i=1;i<=tot;i++)	num[i]+=num[i-1];
    	for(int i=1;i<=tot;i++){
    		pos[num[tree[i].len]]=i;
    		num[tree[i].len]--;
    	}
    	for(int i=tot;i>0;i--)
    		cnt[tree[pos[i]].fa]+=cnt[pos[i]];
    	return;
    }
    

    代碼:

    #include<bits/stdc++.h>
    using namespace std;
    #define in Read()
    #define LL long long
    
    inline int in{
    	int s=0,f=1;char x;
    	for(x=getchar();x<'0'||x>'9';x=getchar())	if(x=='-')	f=-1;
    	for( ;x>='0'&&x<='9';x=getchar())	s=(s<<1)+(s<<3)+(x&15);
    	return f==1?s:-s;
    }
    
    const int A=1e6+5;
    char a[A];
    int n;
    struct SAM{
    	int len,fa;
    	int nex[26];
    }tree[4*A];
    int las,tot;
    int cnt[2*A];
    
    inline void build(){
    	tree[0].len=0,tree[0].fa=-1;
    	las=0;
    	return;
    }
    
    inline void add(int x){
    	int now=++tot;
    	tree[now].len=tree[las].len+1;
    	int p=las;
    	while(p!=-1&&!tree[p].nex[x]){
    		tree[p].nex[x]=now;
    		p=tree[p].fa;
    	}
    	if(p==-1)	tree[now].fa=0;
    	else{
    		int q=tree[p].nex[x];
    		if(tree[p].len+1==tree[q].len)	tree[now].fa=q;
    		else{
    			int cur=++tot;
    			tree[cur].len=tree[p].len+1;
    			tree[cur].fa=tree[q].fa;
    			for(int i=0;i<26;i++)
    				tree[cur].nex[i]=tree[q].nex[i];
    			while(p!=-1&&tree[p].nex[x]==q){
    				tree[p].nex[x]=cur;
    				p=tree[p].fa;
    			}
    			tree[q].fa=tree[now].fa=cur;
    		}
    	}
    	las=now;
    	cnt[now]=1;
    	return;
    }
    
    int num[2*A],pos[2*A];
    
    inline LL get_ans(){
    	for(int i=1;i<=tot;i++)	num[tree[i].len]++;
    	for(int i=1;i<=tot;i++)	num[i]+=num[i-1];
    	for(int i=1;i<=tot;i++){
    		pos[num[tree[i].len]]=i;
    		num[tree[i].len]--;
    	}
    	for(int i=tot;i>0;i--)
    		cnt[tree[pos[i]].fa]+=cnt[pos[i]];
    	LL ans=0;
    	for(int i=1;i<=tot;i++)
    		if(cnt[i]!=1)	ans=max(ans,(LL)cnt[i]*tree[i].len);
    	return ans;
    }
    
    signed main(){
    	scanf("%s",a+1);
    	n=strlen(a+1);
    	build();
    	for(int i=1;i<=n;i++)
    		add(a[i]-'a');
    	printf("%lld\n",get_ans());
    	return 0;
    }
    

    T3 P1368 工藝

    P1368 工藝
    題目描述
    小敏和小燕是一對好朋友。
    他們正在玩一種神奇的游戲,叫MinecraftMinecraft
    他們現在要做一個由方塊構成的長條工藝品。但是方塊現在是亂的,而且由于機器的要求,他們只能做到把這個工藝品最左邊的方塊放到最右邊。
    他們想,在僅這一個操作下,最漂亮的工藝品能多漂亮。
    兩個工藝品美觀的比較方法是,從頭開始比較,如果第i個位置上方塊不一樣那么誰的瑕疵度小,那么誰就更漂亮,如果一樣那么繼續比較第i+1i+1個方塊。如果全都一樣,那么這兩個工藝品就一樣漂亮。

    輸入格式
    第一行兩個整數nn,代表方塊的數目。
    第二行nn個整數,每個整數按從左到右的順序輸出方塊瑕疵度的值。

    輸出格式
    一行n個整數,代表最美觀工藝品從左到右瑕疵度的值。

    輸入輸出樣例
    輸入
    10
    10 9 8 7 6 5 4 3 2 1

    輸出
    1 10 9 8 7 6 5 4 3 2

    說明/提示
    對于100%的數據,n<=300000

    思路:
    一句話題意:求字典序最小的同構序列

    可以用最小表示法

    將字符串拓展成兩倍,處理環,建立后綴自動機,從根節點DFS,貪心走最小字符,走nn次。

    代碼:

    #include<bits/stdc++.h>
    using namespace std;
    #define in Read()
    
    inline int in{
    	int s=0,f=1;char x;
    	for(x=getchar();x<'0'||x>'9';x=getchar())	if(x=='-')	f=-1;
    	for( ;x>='0'&&x<='9';x=getchar())	s=(s<<1)+(s<<3)+(x&15);
    	return f==1?s:-s;
    }
    
    const int A=6e5+5;
    int n;
    int a[A];
    struct SAM{
    	int len,fa;
    	map <int,int> nex;
    }tree[4*A];
    int las,tot;
    
    inline void build(){
    	tree[0].len=0,tree[0].fa=-1;
    	las=0;
    	return;
    }
    
    inline void add(int x){
    	int now=++tot;
    	tree[now].len=tree[las].len+1;
    	int p=las;
    	while(p!=-1&&!tree[p].nex.count(x)){
    		tree[p].nex[x]=now;
    		p=tree[p].fa;
    	}
    	if(p==-1)	tree[now].fa=0;
    	else{
    		int q=tree[p].nex[x];
    		if(tree[p].len+1==tree[q].len)	tree[now].fa=q;
    		else{
    			int cur=++tot;
    			tree[cur].len=tree[p].len+1;
    			tree[cur].fa=tree[q].fa;
    			tree[cur].nex=tree[q].nex;
    			while(p!=-1&&tree[p].nex[x]==q){
    				tree[p].nex[x]=cur;
    				p=tree[p].fa;
    			}
    			tree[now].fa=tree[q].fa=cur;
    		}
    	}
    	las=now;
    	return;
    }
    
    signed main(){
    	n=in;
    	for(int i=1;i<=n;i++)
    		a[i]=a[i+n]=in;
    	build();
    	for(int i=1;i<=2*n;i++)
    		add(a[i]);
    	int pos=0;
    	for(int i=1;i<=n;i++){
    		printf("%d ",tree[pos].nex.begin()->first);
    		pos=tree[pos].nex.begin()->second;
    	}
    	return 0;
    }
    

    T4 SP48 BEADS - Glass Beads

    SP48 BEADS - Glass Beads
    題目描述
    求字典序最小的同構序列的第一個字符在原字符串中的位置

    輸入格式: 輸入的第一行包含一個整數NN,表示輸入數據的組數。接著是NN組數據,每組數據包含一個字符串。每一組數據的長度不超過1000010000個字符。字符均為小寫的英語字母,它們的字典序按照英文字母表的順序確定。

    輸出格式: 對于每一組數據,輸出一行,包含一個整數,代表最差的情況中首顆珠子的編號。這個答案滿足:字符串(代表分割情況)A[i]A[i]的字典序在所有的字符串中是最小的。如果答案不唯一,輸出最小的ii

    輸入輸出樣例
    輸入
    4
    helloworld
    amandamanda
    dontcallmebfu
    aaabaaa

    輸出
    10
    11
    6
    5

    思路:
    同T3,但是要求位置。
    lenlen為指向此節點的邊所代表的字符在數組中的位置,則輸出最終節點的len?n+1len-n+1lenlen為兩倍字符串中取出的末位置)。

    代碼:

    #include<bits/stdc++.h>
    using namespace std;
    #define in Read()
    
    inline int in{
    	int s=0,f=1;char x;
    	for(x=getchar();x<'0'||x>'9';x=getchar())	if(x=='-')	f=-1;
    	for( ;x>='0'&&x<='9';x=getchar())	s=(s<<1)+(s<<3)+(x&15);
    	return f==1?s:-s;
    }
    
    const int A=1e5+5;
    const int INF=1e9;
    int n,m;
    char a[2*A];
    struct SAM{
    	int len,fa;
    	int nex[26];
    }tree[2*A];
    int las,tot;
    int end[2*A];
    
    inline void build(){
    	tree[0].len=0,tree[0].fa=-1;
    	las=tot=0;
    	memset(tree[0].nex,0,sizeof(tree[0].nex));
    	return;
    }
    
    inline void add(int x){
    	int now=++tot;
    	memset(tree[now].nex,0,sizeof(tree[now].nex));
    	tree[now].len=tree[las].len+1;
    	int p=las;
    	while(p!=-1&&!tree[p].nex[x]){
    		tree[p].nex[x]=now;
    		p=tree[p].fa;
    	}
    	if(p==-1)	tree[now].fa=0;
    	else{
    		int q=tree[p].nex[x];
    		if(tree[q].len==tree[p].len+1)	tree[now].fa=q;
    		else{
    			int cur=++tot;
    			tree[cur].len=tree[p].len+1;
    			tree[cur].fa=tree[q].fa;
    			for(int i=0;i<26;i++)
    				tree[cur].nex[i]=tree[q].nex[i];
    			while(p!=-1&&tree[p].nex[x]==q){
    				tree[p].nex[x]=cur;
    				p=tree[p].fa;
    			}
    			tree[now].fa=tree[q].fa=cur;
    		}
    	}
    	las=now;
    	return;
    }
    
    inline void DFS(int x,int dep){
    	if(dep==m){
    		printf("%d\n",tree[x].len-m+1);
    		return;
    	}
    	for(int i=0;i<26;i++)
    		if(tree[x].nex[i]){
    			DFS(tree[x].nex[i],dep+1);
    			break;
    		}
    	return;
    }
    
    signed main(){
    	n=in;
    	while(n--){
    		scanf("%s",a+1);
    		m=strlen(a+1);
    		build();
    		for(int i=1;i<=2*m;i++)
    			add(a[(i-1)%m+1]-'a');
    		DFS(0,0);
    	}
    	return 0;
    }
    
    版權聲明:本文為hongkongreporter原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/hongkongreporter/article/details/104288056

    智能推薦

    后綴自動機概述

    如果對后綴自動機有一定了解,這幾篇文章對你可能會有些許幫助: menci’s后綴自動機學習筆記 后綴自動機學習指南 loj上的后綴自動機講解 一些題目 聽說對拆點講解很詳細 127~132周 以題目為主,當然也有一些講解。下面說一下我對后綴自動機的理解,不給出詳細證明。 后綴自動機的特點 首先,后綴自動機是一種有限狀態自動機,他可以識別且僅識別一個字符串的后綴。但是這不并不是后綴自動機...

    后綴自動機詳解

    轉載自:點我 原論文(俄文)地址:suffix_automata 后綴自動機 后綴自動機(單詞的有向無環圖)——是一種強有力的數據結構,讓你能夠解決許多字符串問題。 例如,使用后綴自動機可以在某一字符串中搜索另一字符串的所有出現位置,或者計算不同子串的個數——這都能在線性 時間內解決。   直覺上,后綴自動機可以被理解為所有子串的簡明信息。...

    后綴自動機詳解

    目錄 前言 簡介 自動機 后綴自動機概念 如何構建后綴自動機 練習題 前言 第\(3\)次嘗試學習后綴自動機…… 下定決心不再背板子 參考資料: 洛谷博客(KesdiaelKen的雷蒻論壇) 2012年noi冬令營clj講稿 前置知識:Trie樹 簡介 后綴自動機,顧名思義是能識別所有后綴的自動機。那么就要從兩個方面入手:什么是自動機,以及怎樣讓自動機識別所有后綴。 其...

    神奇的Batch Normalization 如果一個模型僅訓練BN層會是什么樣的

    您可能會感到驚訝,但這是有效的。 ? 最近,我閱讀了arXiv平臺上的Jonathan Frankle,David J. Schwab和Ari S. Morcos撰寫的論文“Training BatchNorm and Only BatchNorm: On the Expressive Power of Random Features in CNNs”。 這個主意立刻引起了...

    用Python實現校園通知更新提醒

    前言 這個項目實已經在一個月前已經完成了,一直都想寫一篇博客來總結這個過程中遇到的一些問題。但最近一個月來都比較忙,所以一直拖到了現在。 首先說說起因吧,我沒事的時候,總喜歡依次點開學校主頁、教務處、圖書館以及學院的網站,看看有沒有什么新通知,雖然大多與我無關。恰逢最近正在學Python,經常聽到別人說用Python寫爬蟲很簡單,但自己尚未接觸過爬蟲。于是抱著試一試的心態看了幾篇關于Python爬...

    猜你喜歡

    spring_ioc相關_第一章

    1 spring是一站式框架,在javaee的三層結構中,每一層都提供不提并的解決技術 web層:springMVC service層:spring的ioc dao層:spring的jdbcTemplate 2 javaee為避免兩個類之間出現耦合,則把對象的創建交給spring進行管理,spring的ioc操作:(1)ioc的配置文件方式;(2)ioc注解方式 3 ioc的底層原理使用技術(1)...

    【Python+OpenCV】視頻流局部區域像素值處理-一種特征提取方法

    參考我之前寫的處理圖片的文章:Python+OpenCV實現【圖片】局部區域像素值處理(改進版) 開發環境:Python3.6.0 + OpenCV3.2.0 任務目標:攝像頭采集圖像(例如:480*640),并對視頻流每一幀(灰度圖)特定矩形區域(480*30)像素值進行行求和,得到一個480*1的數組,用這480個數據繪制條形圖,即在逐幀采集視頻流并處理后“實時”顯示采...

    JavaWeb——【前端】——注冊頁面

    頁面效果 實現代碼 注意事項 主要使用的bootstrap樣式 如果想引用,不要直接復制,沒用的。 先介紹下所引用的文件: boostrap的js、bootstrap的css、jquery的js、以及自己編寫的register.css。 因為博主用的thymeleaf語法,所以有th符號。 若要使用時,根據個人情況導入相應的依賴。...

    網站HTTP升級HTTPS完全配置手冊

    本文由葡萄城技術團隊于博客園原創并首發 轉載請注明出處:葡萄城官網,葡萄城為開發者提供專業的開發工具、解決方案和服務,賦能開發者。 今天,所有使用Google Chrome穩定版的用戶迎來了v68正式版首個版本的發布,詳細版本號為v68.0.3440.75,上一個正式版v67.0.3396.99發布于6月13日,自Chrome 68起,當在加載非HTTPS站點時,都會在地址欄上明確標記為&ldqu...

    echarts 自定義儀表盤設置背景圖片

    echarts儀表盤 使用插件 vue-echarts 代碼示例 HTML部分 js部分 效果圖...

    精品国产乱码久久久久久蜜桃不卡