题目链接: https://vjudge.net/contest/344930#problem/F
题目大意: 给你 n 个字符串, 让你求给定的两个串的最长公共前缀
题目思路: 处理所给的 n 个字符串的 Hash 值, 然后对于每次给定的两个串, 二分长度就可以了.
值得注意的是这道题需要利用 vector 进行存储
- #include <stdio.h>
- #include <algorithm>
- #include <iostream>
- #include <stdlib.h>
- #include <string>
- #include <string.h>
- #include <math.h>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <map>
- #include <set>
- #define INF 0x3f3f3f3f
- #define LL long long
- typedef unsigned long long ull;
- const int maxn = 1e5+10;
- char s[maxn];
- ull base = 131;
- ull mod = 1e9+7;
- ull p[maxn];
- ull h1[maxn],h2[maxn];
- ull q[maxn];
- int len[maxn];
- std::vector<ull> h[maxn];
- ull get_hash(ull h[],int l,int r){
- return (h[r] - h[l-1]*p[r-l+1]);
- }
- int main() {
- int T;
- int cas = 1;
- scanf("%d",&T);
- while (T--) {
- int n;
- scanf("%d",&n);
- for (int i=1;i<=n;i++) {
- scanf("%s",s+1);
- len[i] = strlen(s+1);
- h[i].clear();
- h[i].push_back(0);
- for (int j=1;j<=len[i];j++) {
- h[i].push_back(h[i][j-1] * base + s[j] - 'a');
- }
- }
- int q;
- printf("Case %d:\n",cas++);
- scanf("%d",&q);
- while (q--) {
- int u,v;
- scanf("%d%d",&u,&v);
- int l = 1,r = std::min(len[u],len[v]);
- int ans = 0;
- while (l <= r) {
- int m = (l + r)>> 1;
- if (h[u][m] == h[v][m]) {
- ans = m;
- l = m + 1;
- }
- else
- r = m - 1;
- }
- printf("%d\n",ans);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3308011.html