芷江建设工程招投标网站,买高端品牌网站,烟台建网站公司哪家好,黑龙江省建设官方网站问题描述 给出一些串#xff0c;多组询问求两个串的最长公共前缀。字符串总长 10^6。 输入格式 第一行一个整数n#xff0c;表示字符串的个数。 接下来n行#xff0c;每行一个字符串#xff08;字符串不含空格#xff09;。 第n2行一个整数m#xff0c;表示询问总数…问题描述 给出一些串多组询问求两个串的最长公共前缀。字符串总长 10^6。 输入格式 第一行一个整数n表示字符串的个数。 接下来n行每行一个字符串字符串不含空格。 第n2行一个整数m表示询问总数。 接下来m行每行两个整数a,b,表示询问第a个字符串和第b个字符串的最长公共前缀的长度。 输出格式 输出共m行对于每个询问输出最长的公共前缀的长度 输入样例 5
abcdef
abcd
acd
cade
abcdef
4
1 2
2 3
1 5
3 4 输出样例 4
1
6
0 限制与约定 1 m 10^6 时间限制1s 空间限制256MB #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includecmath
using namespace std;
const int maxn 1000000 10 ;
int n,ch[maxn][30],val[maxn],cnt,m;
int f[maxn][31],Dep[maxn];
string str[30010];
void dfs(int u,int fa)
{Dep[u]Dep[fa]1;for(int i0;i29;i) f[u][i1]f[f[u][i]][i];for(int i0;i26;i){int v ch[u][i];if(!v) continue;f[v][0]u;dfs(v,u);}
}
void insert(int pos)
{int len str[pos].length(),u0;for(int i0;ilen;i){int x str[pos][i]-a;if(!ch[u][x]) ch[u][x]cnt;uch[u][x];}val[pos]u;
}
int LCA(int x,int y)
{if(Dep[x]Dep[y]) swap(x,y);for(int i30;i0;i--){if(Dep[f[x][i]]Dep[y]) xf[x][i];if(xy) return x;}for(int i30;i0;i--)if(f[x][i]!f[y][i]){xf[x][i];yf[y][i];}return f[x][0];
}
int main()
{cinn;for(int i1;in;i){cinstr[i];insert(i);}dfs(0,-1);cinm;for(int i1,a,b;im;i){scanf(%d%d,a,b);int lcaLCA(val[a],val[b]);printf(%d\n,Dep[lca]-1);}return 0;
} 转载于:https://www.cnblogs.com/hfang/p/11047418.html
