題目鏈接

輸入

第一行包含一個字符串S，S長度不超過50。
第二行包含一個整數N，表示詢問的數目。(1 <= N <= 10)
以下N行每行包括一個S的子串s，s不為空串。

輸出

對于每一個詢問s，求出包含s的狀態st，輸出一行依次包含shortest(st)、longest(st)和endpos(st)。其中endpos(st)由小到大輸出，之間用一個空格分割。

樣例輸入

aabbabd
5
b
abbab
aa
aabbab
bb

樣例輸出

b b 3 4 6
bab aabbab 6
aa aa 2
bab aabbab 6
bb aabb 4

思路

根據后綴自動機的基本概念，暴力枚舉所有子串，統計他們的endpos并用二進制狀態表示。

#include <bits/stdc++.h> #define LL long long #define P pair<int, int> #define lowbit(x) (x & -x) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, a, n) for (int i = a; i <= n; ++i) const int maxn = 1e6+6; #define mid ((l + r) >> 1) #define lc rt<<1 #define rc rt<<1|1 using namespace std; // __int128 read() { __int128 x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f;} // void print(__int128 x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) print(x / 10); putchar(x % 10 + '0');}int main() { #ifndef ONLINE_JUDGE// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout); #endifios::sync_with_stdio(false);cin.tie(0); cout.tie(0);string s;cin >> s;int len = s.size();map<string, LL> ml;map<LL, string> longest, shortest;for (int i = 0; i < len; ++i) {for (int j = 1; j <= len - i; ++j) {string t = s.substr(i, j); LL all = 0;for (int k = 0; k <= len - j; ++k) {string r = s.substr(k, j);if (r == t) all |= 1LL << (k + j);}ml[t] = all;if (j > (int)longest[all].size()) longest[all] = t;if (shortest[all].size() == 0 || (int)shortest[all].size() > j) shortest[all] = t;}}int q;cin >> q;while (q--) {cin >> s;LL tmp = ml[s];cout << shortest[tmp] << " " << longest[tmp];for (int i = 0; ; ++i) {if ((1LL << i) > tmp) break; if ((1LL << i) & tmp) cout << " " << i;}cout << endl;}return 0; }

總結

以上是生活随笔為你收集整理的hihoCoder #1441 : 后缀自动机一·基本概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。