• <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為指向此節點的邊所代表的字符在數組中的位置（也是此節點代表的最長子串的長度）
    fafa（linklink）為出現次數比此節點維護的出現次數多的最長后綴
    nexnex為子節點（類似AC自動機）

    性質：

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

    每一個節點僅維護一類endposendpos（即endposendpos相同的子串在同一個節點中）
    則一個節點中的子串短的必為長的后綴，且子串長度必為一段連續區間
    nexnex構成有向無環圖（字符維護在邊上），fafa構成一棵樹在這里插入圖片描述
    在圖上，任意一條路徑代表的字符串為原字符串的子串
    在樹上，祖宗節點為子節點的后綴，且在原字符串中的出現次數比子節點少（即uu為vv的祖宗，則endpos(v)?endpos(u)endpos(v)\subseteq endpos(u)）
    所以節點uu和vv所對應的字符串的最大公共后綴為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 次操作加入的魔咒字符。
    1≤n≤1000001≤n≤100000。用來表示魔咒字符的數字 xx 滿足 1≤x≤1091≤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+1（lenlen為兩倍字符串中取出的末位置）。

    代碼：

    #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

    智能推薦

    Android中Paint、Canvas的基礎方法用法

    首先paint是畫筆，可以根據paint中的方法設置畫筆的顏色、大小等等屬性，canvas是畫布，用paint畫筆可以在畫布上畫東西 代碼準備： canvas中的方法：（將下面講解的代碼分別放入注釋位置即可使用） 1、繪制單點： 方法：canvas.drawPoint(float x, float y, Paint mPaint); 參數：x：點的x軸位置；y：點的y軸位置；Paint：自定義畫筆...

    十，Future設計模式

    場景介紹 Future模式是多線程開發中非常常見的一種設計模式，它的核心思想是異步調用。這類似我們日常生活中的在線購物流程，帶在購物網看著一件商品時可以提交表單，當訂單完成后就可以在家里等待商品送貨上門。或者說更形象的是我們發送Ajax請求的時候，頁面是異步的進行后臺處理，用戶無需等待請求的結果，可以繼續瀏覽或操作其他內容。 參與角色 Future模式的主要角色有： Main：系統啟動，調用Fut...

    小程序支付系列

      小程序支付，涉及一些知識。 在微信提供的接口文檔中提供了一個微信支付接口，應該是直接調用這個接口就可以發起微信支付 文檔路徑：https://developers.weixin.qq.com/miniprogram/dev/api/api-pay.html#wxrequestpaymentobject          但是，當開始信...

    兩個變量相乘_無廢話學編程基礎（C++篇）3： 變量，賦值語句

    【現實需求】 今天我們要做一個小的應用程序，先說一說需求： 我們日常會去水果店買水果 例如， 蘋果5元/斤 香蕉12元/斤 橘子6元/斤 買完了水果要去結賬了，現在很少看著人手敲計算器了吧。 如果有一個小的應用程序可以解決這個問題不是更好嗎？ 要完成這樣一個小的應用程序，需要知道以下幾個基本概念： 順序結構 變量 語句，賦值語句 輸入和輸出 順序結構 首先我們來看一下什么是程序的順序結構。 寫程序...

    wifi放大器速度_放大器的速度有多快？

    wifi放大器速度 AMP has caused quite the stir from a philosophical perspective, but the technology hasn’t received as close of a look. A few weeks ago, Ferdy Christant wrote about the unfair advantage...

    猜你喜歡

    Java IO講解(一)

    Java IO講解 一、簡介 二、Java IO類庫基本架構 三、Java IO類型劃分 四、既然有了字節流,為什么還要有字符流? 五、字節字符相互轉換 一、簡介 IO(輸入輸出)問題是Web應用所面臨的的主要問題這一，因為在當前這個海量數據時代，數據在網絡中隨處流動。在這個數據流動的過程當中都涉及IO問題，大部分應用系統的瓶頸都是IO瓶頸。 二、Java IO類庫基本架構 ①基于字節操作的抽象類...

    部署HPC集群的實施方案

    部署HPC集群的實施方案 濟南友泉軟件有限公司 一、系統配置 1.1 網絡拓撲 1.2 操作系統 登錄節點：CentOS Linux release 7.3.1611 管理節點：CentOS Linux release 7.3.1611 計算節點：CentOS Linux release 7.9.2009， 二、計算節點、登錄節點配置 2.1 域名設置 在登錄節點、所有計算節點上執行以下命令，完成...

    docker基本介紹&docker鏡像&docker常用命令

    1.docker介紹 2.docker鏡像 3.docker常用管命令 4.dockerfile編寫和應用（真實企業應用） 5.docker中網絡部分講解 1.docker介紹 1.什么是docker Docker 是應用最廣泛的開源容器引擎，讓開發者可以打包他們的應用以及依賴包到一個可移植的容器中 docker實質就像虛擬機一樣，就好像是一個具有獨立操作系統的真實機器 虛擬機是有真正的linux...

    oracle ORA-01033

    描述： 操作系統window10 ，Oracle 11g ,電腦異常斷電，再次打開電腦，連接oracle數據庫實例，報錯 Ora-01033 重啟Oracle各項服務，還是無法連接到數據庫 在查找了相關資料后，使用sqlplus命令，用system 登錄 輸入命令 SQL> shutdown normal SQL> startup mount SQL> alter databas...

    vue+vant的Indexbar索引欄的內容加載問題

    vant的IndexBar使用問題 按照官方的寫法引入 前端渣渣第一次使用vant的IndexBar時遇到的問題；根據公司的業務需求，需要做一個移動端的H5demo, 技術選型使用了vue+vant 按照官方的寫法引入 出現了如下錯誤： 只有標題，沒有內容 根據這個問題想出了解決思路: 參考文檔 vant官方文檔里面沒有引入cell這個組件 解決方法: 在這兩個地方加入Cell 這樣就解決了，va...

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