外贸公司网站如何免费推广,做艺术文字的网站,广州白云手机网站建设,图片上传网站变形的处理题意#xff1a;给一个字符串 SSS#xff0c;以子串的形式给出一些 A 类串和 B 类串以及 mmm 对 A 类串支配 B 类串的关系。求一个总长度最长的 A 类串序列#xff0c;使得每个串都存在一个 B 类串前缀被后一个串支配。无穷输出 −1-1−1。 ∣S∣,m≤2105|S|,m\leq 2\times …题意给一个字符串 SSS以子串的形式给出一些 A 类串和 B 类串以及 mmm 对 A 类串支配 B 类串的关系。求一个总长度最长的 A 类串序列使得每个串都存在一个 B 类串前缀被后一个串支配。无穷输出 −1-1−1。
∣S∣,m≤2×105|S|,m\leq 2\times 10^5∣S∣,m≤2×105
显然需要先把反串 SAM 建出来然后树上倍增定位每个子串。
对于每一步相当于是可以不断丢掉最后一个字符变成前缀如果是个 B 类串可以走到一个被支配的 A 类串。
所以 SAM 上每个点向 fail 树上的父亲连一条 000 的边 uuu 支配 vvv 就从 vvv 往 uuu 连 ∣u∣|u|∣u∣ 的边。然后拓扑排序后做最长路即可。因为没有 000 环也没有不联通等奇奇怪怪的东西所以有环就是 −1-1−1。
然后这道题就做完了……
才怪。你的 AB 类串定位的是一类子串而限制是死的。具体来说一个 B 类串定位到了某个结点的一坨子串上然后一个 A 类串定位也定位到了这个结点而且还比 B 类串短那么它是不能走到这个 B 的。但是 SAM 上它们是同一个结点所以上面的算法就会出错。
怎么办拆了呗
当然不用真的拆了把这些定位的点放结点的 vector 里然后在内部排序建一下就可以了。
不算难写单纯的码量大。
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#include utility
#include queue
#include algorithm
#define MAXN 800005
#define MAXM 1200005
using namespace std;
typedef long long ll;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
char s[MAXN];
int ch[MAXN][26],len[MAXN],fa[MAXN],las1,tot1;
void insert(int c)
{int curtot;len[cur]len[las]1;int plas;for (;p!ch[p][c];pfa[p]) ch[p][c]cur;if (!p) fa[cur]1;else{int qch[p][c];if (len[q]len[p]1) fa[cur]q;else{int _qtot;len[_q]len[p]1;fa[_q]fa[q],fa[cur]fa[q]_q;memcpy(ch[_q],ch[q],sizeof(ch[_q]));for (;pch[p][c]q;pfa[p]) ch[p][c]_q;}}lascur;
}
int up[MAXN][20];
inline void build()
{for (int i1;itot;i) up[i][0]fa[i];for (int j1;j20;j)for (int i1;itot;i)up[i][j]up[up[i][j-1]][j-1];
}
inline int find(int x,int l)
{for (int i19;i0;i--)if (len[up[x][i]]l)xup[x][i];return x;
}
int na,nb,la[MAXN],lb[MAXN],ra[MAXN],rb[MAXN];
struct node
{ int idx,type;inline int len()const{return type? ra[idx]-la[idx]1:rb[idx]-lb[idx]1;}inline int pos()const{if (type1) return totidx;if (type0) return totnaidx;return idx;}
};
inline bool operator (const node a,const node b){return a.len()b.len()||(a.len()b.len()a.typeb.type);}
vectornode lis[MAXN];
struct edge{int u,v,w;}e[MAXM];
int head[MAXN],nxt[MAXM],deg[MAXN],cnt;
inline void addnode(int u,int v,int w)
{e[cnt](edge){u,v,w};nxt[cnt]head[u];head[u]cnt;deg[v];
}
int pos[MAXN],dfn[MAXN],tim;
ll dp[MAXN];
int q[MAXN],qs,qt;
void clear()
{for (int i1;itot;i) {memset(ch[i],0,sizeof(ch[i])),fa[i]len[i]0;memset(up[i],0,sizeof(up[i]));vectornode().swap(lis[i]);}for (int i1;itotnanb1;i) head[i]deg[i]dp[i]0;for (int i1;icnt;i) nxt[i]0;timcnt0,lastot1;
}
int main()
{for (int Tread();T;T--){scanf(%s,s1);int nstrlen(s1);for (int in;i1;i--) insert(s[i]-a),pos[i]las;build(); naread();for (int i1;ina;i){la[i]read(),ra[i]read();lis[find(pos[la[i]],ra[i]-la[i]1)].push_back((node){i,1});}nbread();for (int i1;inb;i){lb[i]read(),rb[i]read();lis[find(pos[lb[i]],rb[i]-lb[i]1)].push_back((node){i,0});}for (int i1;itot;i) {sort(lis[i].begin(),lis[i].end());lis[i].push_back((node){i,-1});if (fa[i]) addnode(lis[i].front().pos(),fa[i],0);for (int j0;j(int)lis[i].size()-1;j) addnode(lis[i][j1].pos(),lis[i][j].pos(),0);}for (int mread();m;m--){int u,v;uread(),vread();addnode(totnav,totu,ra[u]-la[u]1);}int Stotnanb1;for (int i1;ina;i) addnode(S,toti,ra[i]-la[i]1);qs1,qt0;for (int i1;iS;i) if (!deg[i]) q[qt]i;while (qsqt){int udfn[tim]q[qs];for (int ihead[u];i;inxt[i])if (!(--deg[e[i].v]))q[qt]e[i].v;}if (timS) puts(-1);else{for (int kS;k1;k--){int udfn[k];for (int ihead[u];i;inxt[i])dp[u]max(dp[u],dp[e[i].v]e[i].w);}printf(%lld\n,dp[S]);}clear();}return 0;
}
