http://acm.hdu.edu.cn/showproblem.php?pid=5069
首先判断suffix和prefix最长多少可以直接暴力枚举长度然后 + ｈａｓｈ可以立马判断是否相等，复杂度O(lenstr)
现在知道总长度 <= 1e5， magic = sqrt(lenstr)
那么，
如果长度是 <= magic的，最多1e5个询问，每次询问我暴力也是才1e5 * sqrt(1e5)的复杂度。
如果长度是 >= magic的，
第一个极端情况是有magic个不同的串，这样就可以有magic^2个不同的询问，但是这样每个串的长度最长是magic，这样暴力也是才magic * magic * magic = 1e5 * sqrt(1e5)的复杂度。
第二个极端情况是只有2个串，每个串长度都很长，1e5 / 2 的长度，这样暴力一次就需要O(1e5)的复杂度了。但是如果这样的话，不同的询问就会很少，可以用个ans数组存起来,ans[a][b]，这样总复杂度也是 <= 1e5 * sqrt(1e5)的复杂度。
所以总复杂度是nsqrtn
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; const int maxn = 1e5 + 20; char str[maxn]; int po[maxn], suffix[maxn], prefix[maxn]; int be[maxn], en[maxn]; int n, q; int ans[444][444]; int getAns(int one, int two) { for (int i = min(en[two] - be[two] + 1, en[one] - be[one] + 1); i >= 1; --i) { if (prefix[be[two] + i - 1] == suffix[en[one] - i + 1]) { return i; } } return 0; } int pos[maxn]; void work() { scanf("%d%d", &n, &q); int magic = (int)sqrt(n * 1.0); int to = 0; for (int i = 1; i <= n; ++i) { scanf("%s", str + en[i - 1] + 1); int len = strlen(str + en[i - 1] + 1); be[i] = en[i - 1] + 1, en[i] = en[i - 1] + len; prefix[be[i]] = str[be[i]]; for (int j = be[i] + 1; j <= en[i]; ++j) { prefix[j] = prefix[j - 1] * 131 + str[j]; } suffix[en[i]] = str[en[i]]; for (int j = en[i] - 1; j >= be[i]; --j) { suffix[j] = str[j] * po[en[i] - j] + suffix[j + 1]; } if (len > magic) { pos[i] = ++to; } } // printf("%s ", str + 1); // for (int i = 1; i <= n; ++i) { // printf("%d %d ", be[i], en[i]); // } for (int i = 1; i <= to; ++i) { for (int j = 1; j <= to; ++j) { ans[i][j] = -1; } } while (q--) { int one, two; scanf("%d%d", &one, &two); if (en[one] - be[one] + 1 <= magic || en[two] - be[two] + 1 <= magic) { printf("%d ", getAns(one, two)); } else { if (ans[pos[one]][pos[two]] == -1) { ans[pos[one]][pos[two]] = getAns(one, two); } printf("%d ", ans[pos[one]][pos[two]]); } } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif po[0] = 1; for (int i = 1; i <= maxn - 20; ++i) po[i] = po[i - 1] * 131; while (scanf("%d%d", &n, &q) > 0) work(); return 0; }
https://www.nowcoder.com/acm/contest/94/E
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef unsigned long long int LL; const int maxn = 1e6 + 20; char str[maxn]; LL po[maxn], suffix[maxn], prefix[maxn]; int be[maxn], en[maxn]; int n, q; int ans[1000][1000]; int getAns(int one, int two) { for (int i = min(en[two] - be[two] + 1, en[one] - be[one] + 1); i >= 1; --i) { if (prefix[be[two] + i - 1] == suffix[en[one] - i + 1]) { return i; } } return 0; } int pos[maxn]; void work() { int magic = (int)sqrt(300000 * 1.0); int to = 0; for (int i = 1; i <= n; ++i) { scanf("%s", str + en[i - 1] + 1); int len = strlen(str + en[i - 1] + 1); be[i] = en[i - 1] + 1, en[i] = en[i - 1] + len; prefix[be[i]] = str[be[i]]; for (int j = be[i] + 1; j <= en[i]; ++j) { prefix[j] = prefix[j - 1] * 131 + str[j]; } suffix[en[i]] = str[en[i]]; for (int j = en[i] - 1; j >= be[i]; --j) { suffix[j] = str[j] * po[en[i] - j] + suffix[j + 1]; } if (len > magic) { pos[i] = ++to; } } // printf("%s ", str + 1); // for (int i = 1; i <= n; ++i) { // printf("%d %d ", be[i], en[i]); // } for (int i = 1; i <= to; ++i) { for (int j = 1; j <= to; ++j) { ans[i][j] = -1; } } cin >> q; while (q--) { int one, two; scanf("%d%d", &one, &two); if (en[one] - be[one] + 1 <= magic || en[two] - be[two] + 1 <= magic) { printf("%d ", getAns(one, two)); } else { if (ans[pos[one]][pos[two]] == -1) { ans[pos[one]][pos[two]] = getAns(one, two); } printf("%d ", ans[pos[one]][pos[two]]); } } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif po[0] = 1; for (int i = 1; i <= maxn - 20; ++i) po[i] = po[i - 1] * 131; while (scanf("%d", &n) > 0) work(); return 0; }