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

浅谈后缀自动机

时间：2023-03-23 22:48:31浏览次数：37  
标签：Last 浅谈 后缀 Tree Len int Link 自动机 cur

后缀自动机

自动机

首先什么是自动机

我们大多用的是\(DFA\),也就是有限状态自动机

整个自动机是由一些边和点组成的,边上的权为字符

简单理解就是输入一个字符串如果是我们想要接受的，那这个字符串就会按顺序遍历图,并最后会在终止节点停下,是为接受

当然,也有一些字符串无法被接受,比如AC自动机就是接受模式串

后缀相关

我们将以\(i\)为结尾的所有子串建一棵\(Tire\)

很明显这样的\(Tire\)点数是\(n^2\)的,同时它可以接受所有子串的功能

而后缀自动机就是最小化上述的自动机

为了缩小点数,我们可以对一些具有相同性质的点缩点

定义\(R_S\)为子串\(S\)在原串中所有出现位置的右端点组成的集合,我们把相同\(R\)的子串缩成一个点

然后探究一下这样做的正确性与性质

首先对于\(R_X\)与\(R_Y\),如果两者有交集,则一定是包含或被包含的关系

考虑反证,如果存在\(R_X,R_Y\)有交集,在交集的位置,我们假设\(|X|>|Y|\),则\(Y\)是\(X\)的一个子串

对于\(pos\in R_X,\notin R_Y\),其\(|Y|\)一定能在\(pos\)位置匹配到,则\(R_Y\subseteq R_X\)

由此,我们定义\(Link\)表示当前节点\(i\)代表\(R\),\(Link_i\)为\(R\subseteq R'\)最小的\(R'\),也就是从\(R'\)这里选一些子集

注意到\(Link\)形成的是一个树的结构,同时每次连边会划分集合至少两个,因此点数保证一定是\(2*n\)左右

注意区分自动机上的连边和\(Link\)边

自动机的连边是在当前子串\(S\)上加一个字符\(ch\)后\(S+ch\)能匹配到所有的右端点,相当于在后面加字符

而\(Link\)边是为了放大\(R\),相当于在前缀删字符最多删多少,同时注意到一个节点代表的是一段连续的区间,因为删字符得到的前缀一定是连续的,如果设\(Len_i\)表示\(i\)点代表字符串的最长长度,那么\(i\)代表的区间为\([Len_{link_i}+1,Len_i]\)

具体实现

后缀自动机的实现是在线的

记当前末尾位置为\(Lp\),字符为\(ch\)

具体的我们考虑记录\(Last\)表示之前自动机末尾停下的节点,\(cur\)为当前末尾的节点,\(cur\)肯定是连在\(Last\)的后面,边为\(ch\),同时\(Len_{cur}=Len_{Last}+1\)

考虑跳\(Last\)字符串的前缀也就是跳\(Link\)链,假设现在跳到了节点\(P\)如果\(P\)没有\(ch\)边,则直接给它连到\(cur\)

找到第一个有\(ch\)边的\(P\),走\(ch\)边后为\(Q\),如果没找到直接\(Link_{cur}=0\)

考虑如果\(Len_Q=Len_P+1\),则\(P\)接\(ch\)等同于\(Q\)就可以了,\(Link_{cur}=Q\),同时\(Q\)的\(Link\)链上的\(R\)全部插一个\(Lp\)(没必要实现)

如果\(Len_Q>Len_P+1\)，则\(Q\)对应的子串比\(P+ch\)更长,即在\(Link\)树上\(P+ch\)为\(Q\)的父亲,我们复制\(Q\)到\(Clone\),直接\(Link_Q=Link_{cur}=Clone\),同时我们继续爬\(Last\)的\(Link\)链,将所有指向\(Q\)的全部指向\(Clone\)

struct SAM{
	SAM_node Tree[MAXN*2]; 
	int cnt_node;
	int Last;
	void Build()
	{
		cnt_node=0;
		Last=0;
		Tree[0].Link=-1;
		Tree[0].Len=0;
		return;
	}
	void Insert(char s)
	{
		int p=Last;
		int cur=++cnt_node;
		p=Tree[Last].Link;
		Tree[Last].Next[s-'a']=cur;
		Tree[cur].Len=Tree[Last].Len+1;
		while((p!=-1)&&(!Tree[p].Next[s-'a']))
		{
			Tree[p].Next[s-'a']=cur;
			p=Tree[p].Link;
		}		
		if(p==-1)
		{
			Tree[cur].Link=0;
		}
		else
		{
			int q=Tree[p].Next[s-'a'];
			if(Tree[q].Len==Tree[p].Len+1)
			{
				Tree[cur].Link=q;
			}
			else
			{
				int clone=++cnt_node;
				Tree[clone]=Tree[q];
				Tree[clone].Len=Tree[p].Len+1;
				Tree[q].Link=clone;
				Tree[cur].Link=clone;
				while((p!=-1)&&(Tree[p].Next[s-'a']==q))
				{
					Tree[p].Next[s-'a']=clone;
					p=Tree[p].Link;
				}
			}
		}
		Last=cur;
	}
}sam;

一些应用

首先明确一些性质

根节点到每个点的所有路径拼起来就是这个点代表的字符串集合

\(R\)的大小就是这个点出现节点的次数,同时\([Len_{Link_i}+1,Len_i]\)是\(i\)代表节点的长度区间

不同字符串的个数及总长度

考虑每个点的贡献分别为\(Len_i-Len_{Link_i}\)和\(\dfrac{(Len_i+1+Len_{Link_i})(Len_i-Len_{Link_i})}{2}\)

出现次数

每个节点的出现次数就是\(|R|\),我们在插入的时候就在终止节点插一个元素,维护即可

K子串

预处理一下当前节点为起点有多少条路径然后贪心即可

#include <bits/stdc++.h>
const int MAXN = 1e6 + 5;
using namespace std;
struct SAM_node {
    int Len;
    int Next[26];
    int Link;
    int num;
};
struct SAM {

    SAM_node Tree[MAXN * 2];
    int cnt_node;
    int T;
    vector<int>g[MAXN * 2];
    vector<int>G[MAXN * 2];
    int Rd[MAXN * 2];
    long long Dp[MAXN * 2];
    int Last;
    void Build() {
        cnt_node = 0;
        Last = 0;
        Tree[0].Link = -1;
        Tree[0].Len = 0;
        return;
    }
    void Insert(char s) {
        int p = Last;
        int cur = ++cnt_node;
        p = Tree[Last].Link;
        Tree[Last].Next[s - 'a'] = cur;
        Tree[cur].Len = Tree[Last].Len + 1;

        while ((p != -1) && (!Tree[p].Next[s - 'a'])) {
            Tree[p].Next[s - 'a'] = cur;
            p = Tree[p].Link;
        }

        if (p == -1) {
            Tree[cur].Link = 0;
        } else {
            int q = Tree[p].Next[s - 'a'];

            if (Tree[q].Len == Tree[p].Len + 1) {
                Tree[cur].Link = q;
            } else {
                int clone = ++cnt_node;
                Tree[clone] = Tree[q];
                Tree[clone].num = 0;
                Tree[clone].Len = Tree[p].Len + 1;
                Tree[q].Link = clone;
                Tree[cur].Link = clone;

                while ((p != -1) && (Tree[p].Next[s - 'a'] == q)) {
                    Tree[p].Next[s - 'a'] = clone;
                    p = Tree[p].Link;
                }
            }
        }

        Last = cur;
        Tree[cur].num++;
    }
    void Link_Build() {
        for (int i = 0; i <= cnt_node; i++) {
            if (Tree[i].Link != -1) {
                g[Tree[i].Link].push_back(i);
            }

            for (int j = 0; j <= 25; j++) {
                if (!Tree[i].Next[j]) {
                    continue;
                }

                G[Tree[i].Next[j]].push_back(i);
                Rd[i]++;
            }
        }
    }
    void dfs(int x) {
        for (int i = 0; i < g[x].size(); i++) {
            int v = g[x][i];
            dfs(v);
            Tree[x].num += Tree[v].num;
        }
    }
    void Topsort() {
        queue<int>q;

        for (int i = 1; i <= cnt_node; i++) {
            if (!Rd[i]) {

                q.push(i);
            }

            if (!T) {
                Dp[i] = 1;
            } else {
                Dp[i] = Tree[i].num;
            }
        }

        while (q.size()) {
            //      printf(">?");
            int temp = q.front();
            q.pop();

            for (int i = 0; i < G[temp].size(); i++) {
                int v = G[temp][i];
                Rd[v]--;
                Dp[v] += Dp[temp];

                if (Rd[v] == 0) {
                    q.push(v);
                }
            }
        }
    }
    void Rank(int k) {
        int p;

        for (int i = 0; i <= 25; i++) {
            if (!Tree[0].Next[i]) {
                continue;
            }

            int Pox = Tree[0].Next[i];

            if (Dp[Pox] < k) {
                k -= Dp[Pox];
            } else {
                printf("%c", i + 'a');
                p = Pox;
                break;
            }
        }

        while (1) {
            //  printf("???");
            int Kp;

            if (!T) {
                Kp = 1;
            } else {
                Kp = Tree[p].num;
            }

            if (k <= Kp) {
                break;
            } else {
                k -= Kp;
            }

            for (int i = 0; i <= 25; i++) {
                if (!Tree[p].Next[i]) {
                    continue;
                }

                int Pox = Tree[p].Next[i];

                if (Dp[Pox] < k) {
                    k -= Dp[Pox];
                } else {
                    printf("%c", i + 'a');
                    p = Pox;
                    break;
                }
            }
        }

    }
} sam;
string S;
int T;
int k;
int main() {
    cin >> S;
    sam.Build();

    for (int i = 0; i < S.size(); i++) {
        sam.Insert(S[i]);
    }

    scanf("%d %d", &T, &k);
    sam.T = T;
    sam.Link_Build();
    sam.dfs(0);
    sam.Topsort();
    sam.Rank(k);
}

最小循环移位

首先如果存在循环位移,最小循环节长度应该为\(N-Next[N]\)

证明考虑匹配的是\([1,Next[N]]\)段,你将这一段移一下去正好相等

这启示我们直接建\(S+S\)的后缀自动机,在上面找一个与原串相等且右端点最小的即可(相比于KMP空间有点大)

#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<cstring>
const int MAXN=1e6+5;
using namespace std;
struct SAM_node{
	int Len;
	int Next[26];
	int Link;
    int min_num;
};
int Lit;
struct SAM{
	SAM_node Tree[MAXN*2]; 
    vector<int>g[MAXN*2];
	int cnt_node;
	int Last;
	void Build()
	{
		cnt_node=0;
		Last=0;
		Tree[0].Link=-1;
		Tree[0].Len=0;
		return;
	}
    int New()
    {
        ++cnt_node;
        for(int i=0;i<26;i++)
        {
            Tree[cnt_node].Next[i]=0;
        }
        Tree[cnt_node].Link=0;
        Tree[cnt_node].min_num=0x3f3f3f3f;
        Tree[cnt_node].Len=0;
        return cnt_node;
    }
	void Insert(char s,int Pos)
	{
		int p=Last;
		int cur=New();
		p=Tree[Last].Link;
		Tree[Last].Next[s-'a']=cur;
		Tree[cur].Len=Tree[Last].Len+1;
		while((p!=-1)&&(!Tree[p].Next[s-'a']))
		{
			Tree[p].Next[s-'a']=cur;
			p=Tree[p].Link;
		}		
		if(p==-1)
		{
			Tree[cur].Link=0;
		}
		else
		{
			int q=Tree[p].Next[s-'a'];
			if(Tree[q].Len==Tree[p].Len+1)
			{
				Tree[cur].Link=q;
			}
			else
			{
				int clone=++cnt_node;
				for(int i=0;i<26;i++)
                {
                    Tree[clone].Next[i]=Tree[q].Next[i];
                }
                Tree[clone].Link=Tree[q].Link;
				Tree[clone].min_num=0x3f3f3f3f;
				Tree[clone].Len=Tree[p].Len+1;
				Tree[q].Link=clone;
				Tree[cur].Link=clone;
				while((p!=-1)&&(Tree[p].Next[s-'a']==q))
				{
					Tree[p].Next[s-'a']=clone;
					p=Tree[p].Link;
				}
			}
		}
		Last=cur;
		if(Pos>Lit)
        {
            Tree[cur].min_num=min(Tree[cur].min_num,Pos);
        }
	}
    void Link_Build()
	{
        for(int i=0;i<=cnt_node;i++)
        {
            g[i].clear();
        }
		for(int i=0;i<=cnt_node;i++)
		{
			if(Tree[i].Link!=-1)
			{
				g[Tree[i].Link].push_back(i);
            }
		}
	}
	void dfs(int x)
	{
		for(int i=0;i<g[x].size();i++)
		{
			int v=g[x][i];
			dfs(v);
			Tree[x].min_num=min(Tree[v].min_num,Tree[x].min_num);
		}
	}
    int Find(string S)
    {
        int P=0;
        for(int i=0;i<S.size();i++)
        {
            P=Tree[P].Next[S[i]-'a'];
        }
        return Tree[P].min_num;
    }
}sam;
char SS[MAXN];
string S;
int T;
int k;
int main()
{
    while(1)
    {
        cin >> SS;
        S = string(SS, SS+strlen(SS));
        if(S[0]=='.')
        {
            break;
        }
        Lit=S.size();
        sam.cnt_node=0;
        sam.Build();
        for(int i=0;i<S.size();i++)
        {
            sam.Insert(S[i],i+1);
        }  
        for(int i=0;i<S.size();i++)
        {
            sam.Insert(S[i],(i+1)+(int)S.size());
        }
        sam.Link_Build();
        sam.dfs(0);
        int Pd=sam.Find(S);
        if(Pd==0x3f3f3f3f)
        {
            printf("1\n");
        }
        else
        {
            int Lp=(Pd-(S.size()));
            printf("%d\n",int((S.size())/Lp));
        }
    }
 }

第一次出现的位置

很明显维护每一个节点\(R\)集合的最小值

所有出现的位置

维护对应节点的\(R\)即可,大概要用启发式合并？

其实直接遍历子树就行了

最短的没有出现的字符串

一个很zz的问题,就是一层一层的找到第一个连边没有覆盖到所有字符集的节点

两个字符串的最长公共子串

假设有两个串为\(S,T\)

我们对\(S\)建\(SAM\),考虑\(T\)的前\(i\)为的匹配的最长后缀,答案明显显然为最大值

然后考虑优化这个过程,把\(T\)前\(i\)的字符串放进\(SAM\)匹配最长后缀,设当前匹配到\(p\),长度为\(l\)

添加\(T_{i+1}\),如果\(p\)有连边就直接走,否则跳\(Link\)链找第一个满足的

多个字符串的最长公共子串

考虑沿用上道题的思路

同样这样匹配,我们计算在当前\(S_i\)的匹配中节点能匹配的最长长度

而每个节点在多个匹配中的答案显然是每次匹配的最小值

至于最长长度,从\(Link\)树上\(dfs\)即可

#include<bits/stdc++.h>
const int MAXN=1e5+5;
using namespace std;
struct SAM_node{
	int Len;
	int Next[26];
	int Link;
};
struct SAM{
	SAM_node Tree[MAXN*2]; 
	int cnt_node;
	vector<int>g[MAXN*2];
	int Last;
    int mx[MAXN*2];
    int mi[MAXN*2];
    int Flag_Isbuild;
	void Build()
	{
		cnt_node=0;
		Last=0;
		Tree[0].Link=-1;
		Tree[0].Len=0;
		return;
	}
	void Insert(char s)
	{
        if(!Flag_Isbuild)
        {
            Flag_Isbuild=1;
            Build();
        }
		int p=Last;
		int cur=++cnt_node;
		p=Tree[Last].Link;
		Tree[Last].Next[s-'a']=cur;
		Tree[cur].Len=Tree[Last].Len+1;
		while((p!=-1)&&(!Tree[p].Next[s-'a']))
		{
			Tree[p].Next[s-'a']=cur;
			p=Tree[p].Link;
		}		
		if(p==-1)
		{
			Tree[cur].Link=0;
		}
		else
		{
			int q=Tree[p].Next[s-'a'];
			if(Tree[q].Len==Tree[p].Len+1)
			{
				Tree[cur].Link=q;
			}
			else
			{
				int clone=++cnt_node;
				Tree[clone]=Tree[q];
				Tree[clone].Len=Tree[p].Len+1;
				Tree[q].Link=clone;
				Tree[cur].Link=clone;
				while((p!=-1)&&(Tree[p].Next[s-'a']==q))
				{
					Tree[p].Next[s-'a']=clone;
					p=Tree[p].Link;
				}
			}
		}
		Last=cur;
	}
    void LinkB()
	{
		for(int i=0;i<=cnt_node;i++)
		{
			if(Tree[i].Link==-1)
			{
				continue;
			}
			g[Tree[i].Link].push_back(i);
		}
	}
    void dfs(int x)
    { 
        
        for(int i=0;i<g[x].size();i++)
        {
            int v=g[x][i];
            dfs(v);
            mx[x]=max(mx[x],mx[v]);
        }
        mx[x]=min(mx[x],Tree[x].Len);
        mi[x]=min(mi[x],mx[x]);
    }
}sam;
bool cmp(string x,string y)
{
    return x.size()<y.size();
}
string S[15];
int main()
{
  //freopen("date.in","r",stdin);
  // freopen("rnm.out","w",stdout);
    int Cnt;
    scanf("%d",&Cnt);
    for(int i=1;i<=Cnt;i++)
    {
        cin>>S[i];
    }
    sort(S+1,S+1+Cnt,cmp);
    for(int i=0;i<S[1].size();i++)
    {
        sam.Insert(S[1][i]);
    }
    sam.LinkB();
    for(int i=0;i<=sam.cnt_node;i++)
    {
        sam.mi[i]=0x3f3f3f3f;
    }
    for(int C=2;C<=Cnt;C++)
    {
        int p=0;
        int l=0;
        int Ans=0;
        for(int i=0;i<=sam.cnt_node;i++)
        {
             sam.mx[i]=0;
        }
        for(int i=0;i<S[C].size();i++)
        {
            if(sam.Tree[p].Next[S[C][i]-'a'])
            {
                p=sam.Tree[p].Next[S[C][i]-'a'];
                l++;
            }
            else
            {
                while((p!=-1)&&(!sam.Tree[p].Next[S[C][i]-'a']))
                {
                    p=sam.Tree[p].Link;
                    l=sam.Tree[p].Len;
                }
                if(p==-1)
                {
                    p=0;
                    l=0;
                }
                else
                {
                    p=sam.Tree[p].Next[S[C][i]-'a'];
                    l++;
                }

            }
            sam.mx[p]=max(l,sam.mx[p]);
        }

        sam.dfs(0);
    }
    int Ans=0;
    for(int i=sam.cnt_node;i>=1;i--)
    {
        Ans=max(Ans,sam.mi[i]);
    }
    printf("%d\n",Ans);
    
}

标签：Last,浅谈,后缀,Tree,Len,int,Link,自动机,cur
From： https://www.cnblogs.com/kid-magic/p/17249775.html

相关文章

  • 中缀表达式转后缀表达式
      代码实现importjava.util.ArrayList;importjava.util.List;importjava.util.Stack;publicclasstext1{publicstaticvoidmain(String[]args){......
  • 浅谈医用IT隔离电源在DSA手术室配电中的应用
    罗轩志安科瑞电气股份有限公司上海嘉定201801 摘要：随着科技的不断进步，医院的电气设备在不断更新、增多，于是对配电要求越来越高。在确保电气装置的安全和所连接的医用电气......
  • 浅谈活动场景下的图算法在反作弊应用
    作者|ANTI导读随着反作弊与作弊黑产对抗愈发激烈，作弊手段日新月异，我们也不断尝试新的方法解决新的作弊问题。本文主要介绍在活动场景下，应用图算法解决社团类型作弊问题。......
  • 算法 | 中缀表达式转后缀表达式并计算结果（利用栈）
    1.手动实现中缀转后缀2.代码实现中缀转后缀并计算表达式结果为了简化问题，假设算术运算符仅由加、减、乘、除4种运算符和左、右括号组成。step1:声明栈结构#include......
  • js 截取文件后缀名的3种方式
    1.情景展示当我们使用文件上传插件，将文件上传到后台，有时候需要上传的不止一种文件类型，即：图片或着PDF；我们可能需要根据不同文件类型，提供不同的预览地址。如何根据文件......
  • 浅谈电子商务和实体经济
    电子商务和实体经济的分析报告随着信息技术的发展和互联网的普及，电子商务已经成为了一种不可避免的趋势。电子商务不仅改变了人们的购物方式，也对实体经济产生了深远的影响......
  • 牛客14612 string AC自动机 + 树状数组
    传送门题目大意  有T组测试数据，对于每组测试时局有一个n和m，n表示初始拥有的字符串数量，m表示操作数量。紧接着输入n个字符串，再读入m行操作，每行以xstr的形式给出，如果x为......
  • 浅谈树形dp和优化
    树是一个由\(n\)个节点\(n-1\)条边所组成的无向无环连通图。由于每个节点只有一个父亲，可以消除在具体求解中的后效性。一般情况下，我们会采用dfs的方式一边遍历树一边......
  • 浅谈分布式环境下WebSocket消息共享问题
    浅谈分布式环境下WebSocket消息共享问题技术分析我们在开发时会遇到需要使用即时通讯的场景，当然，实现方式很多，Socket、MQTT、Netty....等等。具体用哪种就在于业务的需求......
  • [浅谈] 二维数据结构——树套树
    \(\color{purple}\text{Ⅰ.二维树状数组}\)\(\color{orange}\text{例一：P3372【模板】线段树1}\)$\color{green}\text{2023.1.1014:32}$回忆一下树状数组的区间修改......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99