同学聚会怎么样做网站,广州网站推广多少钱,app源码网站,网络防御中心正题 题目大意
一个字符串SSS#xff0c;给出若干个l,rl,rl,r 求SSS以lll和rrr结尾的前缀一个公共后缀且它是SSS的前缀的子串。 求有多少和最长的那个的长度 解题思路
首先后缀前缀很容易想到KMPKMPKMP#xff0c;我们先处理出nextnextnext数组 然后从(l,r)(l,r)(l,r)开始让…正题 题目大意
一个字符串SSS给出若干个l,rl,rl,r 求SSS以lll和rrr结尾的前缀一个公共后缀且它是SSS的前缀的子串。 求有多少和最长的那个的长度 解题思路
首先后缀前缀很容易想到KMPKMPKMP我们先处理出nextnextnext数组 然后从(l,r)(l,r)(l,r)开始让lll和rrr跳到它们的nextnextnext的位置知道两个相等就好了
但是这样会TTT飞那么我们发现可以将问题转换 每次将(nexti,i)(next_i,i)(nexti,i)连边就变成了一棵树然后求LCALCALCA和它的深度就好了 codecodecode
#includecstdio
#includealgorithm
#includecstring
#includequeue
#includecmath
#define N 31000
using namespace std;
struct line{int to,next,w;
}a[N*5];
int tot,n,m,x,y,ls[N],dep[N],f[N][30],dis[N][30],t,next[N];
char s[N];
queueint q;
inline int readn()
{int X0,w0; char c0;while(c0||c9) {w|c-;cgetchar();}while(c0c9) X(X3)(X1)(c^48),cgetchar();return w?-X:X;
}
inline void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
inline void bfs(int s)
{q.push(s);dep[s]1;while(!q.empty()){int xq.front();q.pop();for (int ils[x];i;ia[i].next){int ya[i].to;if (dep[y]) continue;q.push(y);f[y][0]x;dep[y]dep[x]1;dis[y][0]a[i].w;}}t(int)(log(n)/log(2))1;for (int j1;jt;j){for (int i0;in;i){f[i][j]f[f[i][j-1]][j-1];dis[i][j]min(dis[i][j-1],dis[f[i][j-1]][j-1]);}}
}
inline int LCA(int x,int y)
{if (dep[x]dep[y]) swap(x,y);for (int it;i0;i--)if (dep[f[y][i]]dep[x]) yf[y][i];if (xy) return x;for (int it;i0;i--)if (f[y][i]!f[x][i]) {xf[x][i];yf[y][i];}return f[x][0];
}
void Kmp_build()
{for(int i2,j0;in;i){while(j(s[i]!s[j1])) jnext[j];j(s[i]s[j1]);next[i]j;}for(int i1;in;i)addl(next[i],i,1);
}
int main()
{scanf(%s,s1);nstrlen(s1);Kmp_build();bfs(0);scanf(%d,m);for(int i1;im;i){int l,r,ans;scanf(%d%d,l,r);ansLCA(l,r);printf(%d %d\n,dep[ans]-1,ans);}
}
