微信公众号的h5网站开发6,怎么使用创客贴网站做图,seo网络推广技术,精准拓客营销系统文章目录后缀自动机算法实现过程模板习题洛谷后缀自动机模板题品酒大会[HEOI2015]最短不公共子串字符串蒟蒻写这篇blogblogblog主要是存一下#xff0c;后缀自动机的详细搭建过程#xff0c;方便以后复习 具体的某些证明#xff0c;为什么这么做#xff0c;正确性劈里啪啦一…
文章目录后缀自动机算法实现过程模板习题洛谷后缀自动机模板题品酒大会[HEOI2015]最短不公共子串字符串蒟蒻写这篇blogblogblog主要是存一下后缀自动机的详细搭建过程方便以后复习 具体的某些证明为什么这么做正确性劈里啪啦一大堆就不赘述了讲解指路☞
后缀自动机 后缀自动机上每一条到iii的路径对应一个子串整个自动机包含了字符串的所有子串 很多时候可以和后缀数组等价使用 endposendposendpos一个子串iii在整个字符串中出现的位置 最后一个字符的下标 构成的集合 举个栗子 abcbcdeabcabcbcdeabcabcbcdeabc(从000开始标号) 子串abcabcabc对应的endposendposendpos为{2,9}\{2,9\}{2,9}子串bcbcbc的endposendposendpos为{2,4,9}\{2,4,9\}{2,4,9}
后缀自动机的编号对应的就是endposendposendpos完全相同的所有子串 依旧是上面的粒子abcbcdeabcabcbcdeabcabcbcdeabc 子串bcbcbc的endposendposendpos为{2,4,9}\{2,4,9\}{2,4,9}子串ccc的endposendposendpos也为{2,4,9}\{2,4,9\}{2,4,9} 那么后缀自动机上对应的ididid编号既表示bcbcbc子串也表示ccc子串
算法实现过程 e.g.1e.g.1e.g.1构建abcdabcdabcd的后缀自动机 Ⅰ最初始状态仅有一个空根last1last1last1lastlastlast表示后缀自动机的最后一个节点 Ⅱ 将′a′a′a′扔进去新建一个节点cnt2cnt2cnt2lenlen[last]11lenlen[last]11lenlen[last]11 从lastlastlast开始跳发现111没有′a′a′a′边 则建立一条′a′a′a′边并指向新点222 此时跳到了初始源点222的后缀链接只能指向111lastlastlast变为222 Ⅲ 将′b′b′b′扔进去新建一个节点cnt3,lenlen[last]12cnt3,lenlen[last]12cnt3,lenlen[last]12 从lastlastlast开始跳后缀链接 222没有′b′b′b′边新建一条并指向333跳后缀链接到111 111没有′b′b′b′边新建一条并指向333 此时已经到了根节点333的后缀链接只能指向111last3last3last3 Ⅳ 将′c′c′c′扔进去新建一个节点cnt4,len3cnt4,len3cnt4,len3 从lastlastlast开始跳后缀链接 333没有′c′c′c′边新建一条并指向444跳后缀链接到111 111没有′c′c′c′边新建一条并指向444 此时已经到了根节点444的后缀链接只能指向111last4last4last4 Ⅴ 将′d′d′d′扔进去新建一个节点cnt5,len4cnt5,len4cnt5,len4 从lastlastlast开始跳后缀链接 444没有′c′c′c′边新建一条并指向555跳后缀链接到111 111没有′c′c′c′边新建一条并指向555 此时已经到了根节点555的后缀链接只能指向111last5last5last5 最简单的一种后缀自动机就完成了 接下来就尝试一下进阶版 e.g.2e.g.2e.g.2构建ababeababeababe的后缀自动机 Ⅰ先搭建空源点last1last1last1 Ⅱ 加入′a′a′a′新建一个节点cnt2,len[2]len[last]11cnt2,len[2]len[last]11cnt2,len[2]len[last]11 111没有′c′c′c′边新建一条并指向222 此时已经到了根节点222的后缀链接只能指向111last2last2last2 Ⅲ 加入′b′b′b′新建一个节点cnt3,len[3]len[last]12cnt3,len[3]len[last]12cnt3,len[3]len[last]12 从lastlastlast开始跳后缀链接 222没有′b′b′b′边新建一条并指向333跳后缀链接到111 111没有′b′b′b′边新建一条并指向333 此时已经到了根节点333的后缀链接只能指向111last3last3last3 Ⅳ 再加入′a′a′a′新建一个节点cnt4,len[4]len[last]13cnt4,len[4]len[last]13cnt4,len[4]len[last]13 从lastlastlast开始跳后缀链接 333没有′a′a′a′边新建一条并指向444跳后缀链接到111 111有一条指向222的′a′a′a′边满足len[2]len[1]1len[2]len[1]1len[2]len[1]1则直接将444后缀链接指向222 结束last4last4last4 Ⅴ 再加入′b′b′b′新建一个节点cnt5,len[5]len[last]14cnt5,len[5]len[last]14cnt5,len[5]len[last]14 从lastlastlast开始跳后缀链接 444没有′b′b′b′边新建一条并指向555跳后缀链接到222 222有一条指向333的′b′b′b′边满足len[3]len[2]1len[3]len[2]1len[3]len[2]1直接将555后缀链接指向333 结束last5last5last5 Ⅵ 加入新′c′c′c′新建一个节点cnt6,len[6]len[last]15cnt6,len[6]len[last]15cnt6,len[6]len[last]15 从lastlastlast开始跳后缀链接 555没有′c′c′c′边新建一条并指向666跳后缀链接到333 333没有′c′c′c′边新建一条并指向666跳后缀链接到111 111没有′c′c′c′边新建一条并指向666 此时已到根节点666只能链接111last6last6last6结束 这就是进阶版了没有涉及到最终版的点复制 最后让我们一起携手走进最终版的后缀自动机构造 e.g.3e.g.3e.g.3构建cababcababcabab的后缀自动机 Ⅰ 创造新源点last1,cnt1last1,cnt1last1,cnt1 Ⅱ 加入′c′c′c′新建一个节点cnt2,len[2]len[last]11cnt2,len[2]len[last]11cnt2,len[2]len[last]11 从lastlastlast开始跳后缀链接 111没有′c′c′c′边新建一条并指向222 此时已到根节点222只能链接1,last21,last21,last2 Ⅲ 加入′a′a′a′新建一个节点cnt3,len[3]len[last]12cnt3,len[3]len[last]12cnt3,len[3]len[last]12 从lastlastlast开始跳后缀链接 222没有′a′a′a′边新建一条并指向333跳后缀链接到111 111没有′a′a′a′边新建一条并指向333 此时已到根节点333只能链接1,last31,last31,last3 Ⅳ 加入′b′b′b′新建一个节点cnt4,len[4]len[last]13cnt4,len[4]len[last]13cnt4,len[4]len[last]13 从lastlastlast开始跳后缀链接 333没有′b′b′b′边新建一条并指向444跳后缀链接到111 111没有′a′a′a′边新建一条并指向444 此时已到根节点444只能链接1,last41,last41,last4 Ⅴ 加入′a′a′a′新建一个节点cnt5,len[5]len[last]14cnt5,len[5]len[last]14cnt5,len[5]len[last]14 从lastlastlast开始跳后缀链接 444没有′a′a′a′边新建一条并指向555跳后缀链接到111 111有′a′a′a′边指向333但是len[3]≠len[1]1len[3]≠len[1]1len[3]len[1]1不能像进阶版直接链接这里必须要点复制 新建一个333的分身节点cnt6cnt6cnt6 333的所有信息出入边除了原字符串间的边图中黑色边全部修改为分点666的边直接覆盖 并且666成为333的直接后缀链接替代111 len[6]len[1]11len[6]len[1]11len[6]len[1]11 相当于666做了1,31,31,3后缀链之间的承接点保证了每一条边上lenlenlen只会带来111的影响 555直接链接666后结束last5last5last5 Ⅵ 加入′b′b′b′新建节点cnt7cnt7cnt7 从lastlastlast开始跳后缀链接 555没有′b′b′b′边新建一条指向777跳后缀链接到666 666有一条′b′b′b′边指向444判断len[4]≠len[6]1len[4]≠len[6]1len[4]len[6]1 再次执行复制操作 新建一个444的分身节点cnt8cnt8cnt8 444的所有信息出入边除了原字符串间的边图中黑色边全部修改为分点888的边直接进行覆盖 888成为444的直接后缀链接len[8]len[6]12len[8]len[6]12len[8]len[6]12 777直接链接888后结束last7last7last7
⚡ len[x]len[x]len[x]复制点的lenlenlen不等于被复制点的原后缀链接的len1len1len1而是谁触发的len1len1len1 模板
struct node {int len; //长度int fa; //后缀链接int son[maxc]; //字符集大小
}t[maxn];模拟从主链的前一个开始跳后缀链接并对于链接上的没有该字符边的每一个点都连出一条新字符边
while( pre ! t[pre].son[c] ) t[pre].son[c] now, pre t[pre].fa;跳到根代表这是首个出现的字符他只能链接最初的根节点了
if( ! pre ) t[now].fa 1;否则如果路上找到了满足lenlenlen的关系直接后缀链接指过去即可
int u t[pre].son[c];
if( t[u].len t[pre].len 1 ) t[now].fa u;复制该点并进行有关该点的所有信息重改 ①原点连出的点新点也要连出 ②连入原点的点变成连入新点 ③原点和新点间也需建立联系新点是原点的后缀链接
else {int v tot;t[v] t[u];//利用结构体巧妙将原点连出的点进行复制t[v].len t[pre].len 1;//由谁触发 len就是触发点len1t[u].fa t[now].fa v;//原点与复制点与新建点的关系while( pre t[pre].son[c] u ) t[pre].son[c] v, pre t[pre].fa;//暴力复制修改连入原点的点
}习题
洛谷后缀自动机模板题
code
#include cstdio
#include vector
#include cstring
using namespace std;
#define maxn 2000005
vector int G[maxn];
struct node {int fa, len;int son[30];
}t[maxn];
char s[maxn];
int last 1, tot 1;
long long ans;
int siz[maxn];void insert( int c ) {int pre last, now last tot;siz[tot] 1;t[now].len t[pre].len 1;while( pre ! t[pre].son[c] ) t[pre].son[c] now, pre t[pre].fa;if( ! pre ) t[now].fa 1;else {int u t[pre].son[c];if( t[u].len t[pre].len 1 ) t[now].fa u;else {int v tot;t[v] t[u];t[v].len t[pre].len 1;t[u].fa t[now].fa v;while( pre t[pre].son[c] u ) t[pre].son[c] v, pre t[pre].fa;}}
}void dfs( int u ) {for( int i 0;i G[u].size();i ) {int v G[u][i];dfs( v );siz[u] siz[v];}if( siz[u] ! 1 ) ans max( ans, 1ll * siz[u] * t[u].len );
}int main() {scanf( %s, s );int len strlen( s );for( int i 0;i len;i ) insert( s[i] - a ); for( int i 2;i tot;i ) G[t[i].fa].push_back( i );dfs( 1 );printf( %lld, ans );return 0;
}品酒大会
solution 有一个SAMSAMSAM常用结论前缀i,ji,ji,j的最长公共后缀parenttreeparent\ treeparent tree上前缀i,ji,ji,j分别指向的点u,vu,vu,v的lcalcalca反映在后缀自动机上的节点代表的最长子串 将本题的字符串倒过来建后缀自动机在自动机上进行树上dpdpdp最后从后往前进行更新即可code
#include cstdio
#include vector
#include cstring
#include iostream
using namespace std;
#define inf 0x7f7f7f7f
#define int long long
#define maxn 600005
struct node {int len, fa;int son[30];
}t[maxn];
vector int G[maxn];
int last 1, cnt 1, n;
char s[maxn];
int a[maxn], f[maxn], tot[maxn], siz[maxn], maxx[maxn], minn[maxn];void insert( int x, int w ) {int pre last, now last cnt;siz[now] 1, t[now].len t[pre].len 1;maxx[now] minn[now] w;while( pre ! t[pre].son[x] ) t[pre].son[x] now, pre t[pre].fa;if( ! pre ) t[now].fa 1;else {int u t[pre].son[x];if( t[u].len t[pre].len 1 ) t[now].fa u;else {int v cnt;maxx[v] -inf, minn[v] inf;t[v] t[u];t[v].len t[pre].len 1;t[u].fa t[now].fa v;while( pre t[pre].son[x] u ) t[pre].son[x] v, pre t[pre].fa;}}
}bool check( int u ) {return maxx[u] ! -inf minn[u] ! inf;
}void dfs( int u ) {for( int i 0;i G[u].size();i ) {int v G[u][i];dfs( v );tot[t[u].len] siz[u] * siz[v];siz[u] siz[v];if( check( u ) )f[t[u].len] max( f[t[u].len], max( maxx[u] * maxx[v], minn[u] * minn[v] ) );maxx[u] max( maxx[u], maxx[v] );minn[u] min( minn[u], minn[v] );}
}signed main() {memset( f, -0x7f, sizeof( f ) );scanf( %d %s, n, s 1 );for( int i 1;i n;i )scanf( %lld, a[i] );for( int i n;i;i -- ) insert( s[i] - a, a[i] ); for( int i 2;i cnt;i ) G[t[i].fa].push_back( i );dfs( 1 );for( int i n - 1;~ i;i -- ) tot[i] tot[i 1], f[i] max( f[i], f[i 1] );for( int i 0;i n;i )printf( %lld %lld\n, tot[i], ( tot[i] ? f[i] : 0 ) );return 0;
}[HEOI2015]最短不公共子串
solution 做此题需要了解序列自动机 然后就是很无脑的四个bfsbfsbfs跑 子串就是跑后缀自动机 子序列就是跑序列自动机code
#include queue
#include cstdio
#include cstring
using namespace std;
#define maxn 5000
char a[maxn], b[maxn];struct SAM {struct node {int len, fa;int son[30];}t[maxn];int last, cnt;SAM() {last cnt 1;}void insert( int x ) {int pre last, now last cnt;t[now].len t[pre].len 1;while( pre ! t[pre].son[x] ) t[pre].son[x] now, pre t[pre].fa;if( ! pre ) t[now].fa 1;else {int u t[pre].son[x];if( t[u].len t[pre].len 1 ) t[now].fa u;else {int v cnt;t[v] t[u];t[v].len t[pre].len 1;t[u].fa t[now].fa v;while( pre t[pre].son[x] u ) t[pre].son[x] v, pre t[pre].fa;}}}}SamA, SamB;struct SEQ {int nxt[maxn][30], last[30];SEQ() {memset( nxt, 0, sizeof( nxt ) );memset( last, 0, sizeof( last ) );}void build( int n, char *s ) {for( int i n;~ i;i -- ) {for( int j 0;j 26;j )if( last[j] ) nxt[i 1][j] last[j];if( i ) last[s[i] - a] i 1;}}}SeqA, SeqB;struct node {int x, y, dep;node(){}node( int X, int Y, int Dep ) {x X, y Y, dep Dep;}
};
queue node q;
bool vis[maxn][maxn];void init() {memset( vis, 0, sizeof( vis ) );while( ! q.empty() ) q.pop();vis[1][1] 1, q.push( node( 1, 1, 0 ) );
}int bfs1() {init();while( ! q.empty() ) {node now q.front(); q.pop();for( int i 0;i 26;i ) {int sonA SamA.t[now.x].son[i];int sonB SamB.t[now.y].son[i];if( vis[sonA][sonB] ) continue;else if( sonA ! sonB ) return now.dep 1;else if( sonA sonB ) {vis[sonA][sonB] 1;q.push( node( sonA, sonB, now.dep 1 ) );}}}return -1;
}int bfs2() {init();while( ! q.empty() ) {node now q.front(); q.pop();for( int i 0;i 26;i ) {int sonA SamA.t[now.x].son[i];int sonB SeqB.nxt[now.y][i];if( vis[sonA][sonB] ) continue;else if( sonA ! sonB ) return now.dep 1;else if( sonA sonB ) {vis[sonA][sonB] 1;q.push( node( sonA, sonB, now.dep 1 ) );}}}return -1;
}int bfs3() {init();while( ! q.empty() ) {node now q.front(); q.pop();for( int i 0;i 26;i ) {int sonA SeqA.nxt[now.x][i];int sonB SamB.t[now.y].son[i];if( vis[sonA][sonB] ) continue;else if( sonA ! sonB ) return now.dep 1;else if( sonA sonB ) {vis[sonA][sonB] 1;q.push( node( sonA, sonB, now.dep 1 ) );}}}return -1;
}int bfs4() {init();while( ! q.empty() ) {node now q.front(); q.pop();for( int i 0;i 26;i ) {int sonA SeqA.nxt[now.x][i];int sonB SeqB.nxt[now.y][i];if( vis[sonA][sonB] ) continue;else if( sonA ! sonB ) return now.dep 1;else if( sonA sonB ) {vis[sonA][sonB] 1;q.push( node( sonA, sonB, now.dep 1 ) );}}}return -1;
}int main() {scanf( %s %s, a 1, b 1 );int lena strlen( a 1 ), lenb strlen( b 1 );for( int i 1;i lena;i )SamA.insert( a[i] - a );for( int i 1;i lenb;i )SamB.insert( b[i] - a );SeqA.build( lena, a );SeqB.build( lenb, b );printf( %d\n%d\n%d\n%d\n, bfs1(), bfs2(), bfs3(), bfs4() );return 0;
} 字符串
solution
这题运用的思想主要是广义后缀自动机即将多个字符串建在一个后缀自动机上 其实并没有什么新颖之处只需在扩展的时候带一个这个字符属于哪个字符串的编号即可
假设已经建好了自动机接下来考虑两个长度为kkk的子串之间如何一一对应修改 这个时候如果将其放到parenttreeparent\ treeparent tree上考虑的话就简单了
其实可以猜想一下刚开始我就想到了虚树的性质即相邻两两配对 不难证明的确应该相邻两个不同属类的子串配对
前缀i,ji,ji,j的最长公共后缀parenttreeparent\ treeparent tree上前缀i,ji,ji,j分别指向的点u,vu,vu,v的lcalcalca反映在后缀自动机上的节点代表的最长子串
也就是最后变成深搜一棵树的模样记得特判可能lcalcalca代表的最长子串长度≥k\ge k≥k 此时是不需要代价的
code
#include cstdio
#include vector
#include iostream
#include algorithm
using namespace std;
#define maxn 600005
struct node {int len, fa;int son[30];
}t[maxn];
vector int G[maxn];
int n, k, last 1, cnt 1;
long long ans;
char a[maxn], b[maxn];
int type[maxn];
int tot[maxn][3];void insert( int x, int s, int pos ) {int pre last, now last cnt;t[now].len t[pre].len 1;while( pre ! t[pre].son[x] ) t[pre].son[x] now, pre t[pre].fa;if( ! pre ) t[now].fa 1;else {int u t[pre].son[x]; if( t[u].len t[pre].len 1 ) t[now].fa u;else {int v cnt;t[v] t[u];t[v].len t[pre].len 1;t[u].fa t[now].fa v;while( pre t[pre].son[x] u ) t[pre].son[x] v, pre t[pre].fa;}}if( pos k ) type[now] s;
}void dfs( int u ) {tot[u][type[u]] ;for( int i 0;i G[u].size();i ) {int v G[u][i];dfs( v );tot[u][1] tot[v][1];tot[u][2] tot[v][2];}if( tot[u][1] tot[u][2] ) {int x max( 0, k - t[u].len );ans 1ll * x * tot[u][2];tot[u][1] - tot[u][2];tot[u][2] 0;}else {int x max( 0, k - t[u].len );ans 1ll * x * tot[u][1];tot[u][2] - tot[u][1];tot[u][1] 0;}
}int main() {scanf( %d %d %s %s, n, k, a 1, b 1 );reverse( a 1, a n 1 );reverse( b 1, b n 1 );for( int i 1;i n;i ) insert( a[i] - a, 1, i );for( int i 1;i n;i ) insert( b[i] - a, 2, i );for( int i 2;i cnt;i ) G[t[i].fa].push_back( i );dfs( 1 );printf( %lld, ans );return 0;
}
