台州网站建设咨询薇,网站版权文字,删除wordpress搜索缓存,WordPress任务发布插件题目描述#xff1a;给定一个长串 $S$#xff0c;给定若干 $S$ 的子串 $a_{i}$, $b_{i}$#xff0c;再给出一些 $a$ 串和 $b$ 串的支配关系. 构造一个长度最长的字符串#xff0c;使得#xff1a;字符串只由 $a_{i}$ 组成.当且仅当 $a_{i}$ 所支配的一个串 $b_{i}$ 为 $a_…题目描述给定一个长串 $S$给定若干 $S$ 的子串 $a_{i}$, $b_{i}$再给出一些 $a$ 串和 $b$ 串的支配关系. 构造一个长度最长的字符串使得字符串只由 $a_{i}$ 组成.当且仅当 $a_{i}$ 所支配的一个串 $b_{i}$ 为 $a_{j}$ 的前缀才可将 $a_{j}$ 连到 $a_{i}$ 后面. 首先对于求前缀我们可以对 $S$ 的反串建立后缀自动机这样每个 $f_{i}$ 将会转移到当前串的一个前缀而不是后缀. 第一步先将所有的 $a$串和$b$串都定位到后缀自动机上.对于这一步我们使用倍增算法. 第二部我们将支配边进行连边即再后缀树中对应的点和点). 顺着后缀树中的边和支配边进行转移即可.细节部分看一下代码. Code: #include cstdio
#include algorithm
#include cstring
#include queue
#include vector
#define setIO(s) freopen(s.in,r,stdin)// ,freopen(s.out,w,stdout)
#define maxn 1500001
using namespace std;
char str[maxn];
int debug;
int length,na,nb,m;
namespace SAM{#define N 29 #define ll long long #define L llength-l1#define R rlength-r1 int last,tot; vectorinted[maxn]; int la[maxn],ra[maxn],h[maxn]; int ch[maxn][N],dis[maxn]; int f[maxn],trace[maxn],mk[maxn],pos[maxn]; int F[24][maxn]; int head[maxn],to[maxn],nex[maxn],edges; int ge[maxn]; int vis[maxn]; int trc; queueintQ; int du[maxn]; long long DP[maxn]; int idx[maxn]; int cmp(int i,int j){ if(h[i]h[j]) return ij; return h[i]h[j]; }void add(int u,int v){nex[edges] head[u],head[u]edges,to[edges]v; mk[edges]0; //if(!debug) printf(%d %d\n,u,v); }//SAM of S void ins(int c,int i){ int np tot, p last; last np; dis[np] i; while(p !ch[p][c]) ch[p][c] np, p f[p]; if(!p) f[np] 1;else { int q ch[p][c]; if(dis[q] dis[p] 1) f[np] q;else {int nq tot; dis[nq] dis[p] 1; memcpy(ch[nq],ch[q],sizeof(ch[q])); f[nq] f[q], f[np] f[q] nq; while(p ch[p][c] q) ch[p][c] nq,p f[p]; }}trace[i] np; } void DFS(int u){ F[0][u]f[u];for(int i1;i24;i) F[i][u]F[i-1][F[i-1][u]]; int szed[u].size(); for(int i0;isz;i) DFS(ed[u][i]); ed[u].clear(); } void build(){int l,r;scanf(%d,na);for(int i1;ina;i){scanf(%d%d,l,r); L;R; swap(l,r); la[i]l,ra[i]r,h[i]r-l1; } scanf(%d,nb); for(int i1;inb;i) {scanf(%d%d,l,r); L;R; swap(l,r); la[ina]l,ra[ina]r,h[ina]r-l1; }for(int i2;itot;i) ed[f[i]].push_back(i); trctot; DFS(1); for(int i1;inanb;i) {int ptrace[ra[i]]; for(int j23;j0;--j) if(dis[F[j][p]] h[i]) pF[j][p]; if(dis[p]h[i]) pos[i]p; else ed[p].push_back(i); }}void sol(){int nntot; for(int i2;inn;i){ if(ed[i].size()0){ add(f[i],i); continue; }int p0; int szed[i].size(); for(int j0;jsz;j) ge[p]ed[i][j]; // sort(ge1,ge1p,cmp); //将该点对应字符串按长度排序 int lstf[i]; for(int j1;jp;j) { add(lst,tot); dis[tot] h[ge[j]]; pos[ge[j]]tot; lsttot; }add(pos[ge[p]],i); ed[i].clear(); }}void get(){int a,b; scanf(%d%d,a,b); add(pos[a],pos[bna]); mk[edges]1; } void solve(){Q.push(1); du[1]0; long long ans0; for(int i1;iedges;i) du[to[i]]; while(!Q.empty()){int uQ.front(); Q.pop(); for(int ihead[u];i;inex[i]){--du[to[i]]; long long edDP[u]dis[to[i]]-(mk[i]?0:dis[u]); DP[to[i]]max(DP[to[i]],ed); if(du[to[i]]0) Q.push(to[i]); }} for(int i1;itot;i) if(du[i]!0) {printf(-1\n); return; }for(int i1;ina;i) ansmax(ans,DP[pos[i]]); printf(%lld\n,ans); }void init(){for(int i1;itot;i) DP[i]0; for(int i1;itot;i) dis[i]0; for(int i1;iedges;i) mk[i]0; for(int i1;itot;i) head[i]0; for(int i0;itot;i) du[i]0; for(int i1;itrc;i) for(int j0;j22;j) F[j][i]0; for(int i1;itrc;i) memset(ch[i],0,sizeof(ch[i])); lasttot1,edges0; }
};
int main(){//setIO(string9); int T; scanf(%d,T); while(T--){ debugT; SAM::lastSAM::tot1; scanf(%s,str1),lengthstrlen(str1); for(int ilength;i;--i) SAM::ins(str[i]-a,length-i1); SAM::trcSAM::tot; SAM::build(); SAM::sol(); scanf(%d,m); for(int i1;im;i) SAM::get(); SAM::solve(); SAM::init(); }return 0;
}转载于:https://www.cnblogs.com/guangheli/p/10679544.html
