CF1063F String Journey

【题意】
给你一个字符串，让你从中提取处最多的连续子串，使得这些连续子串在次序保持稳定的环境下满足后一个是前一个的真子串（必须非空）。
【思绪】
这道题给我了一个重要的启发：就是一下子理不清晰思绪的时候可以打一个暴力，然后再思索怎么优化这个暴力。最开始我想直接想正解发现思绪非常的混乱，想了很久没有弄懂。但是打完了暴力以后就可以一目了然的看出要怎么优化了。
先把字符串反转，那么条件就变成了前一个是后一个的子串了。
观察一下发现几个性子：
1.后一个的长度是前一个的长度+1，即在后一个串的前面大概后面多加上一个字母，接下来我们逼迫这个条件满足
2. 如果某个串                                   S                              S                  S可以被提取出来（显然此前已经提取过了长度为1,2,…,|S|-1的串)，那么它的任何一个子段都能被提取出来
然后我们写出一个时间空间都是                                   O                         (                         n                                   n                                  )                              O(n\sqrt n)                  O(nn            ​)的暴力，由于最多有                                             n                                       \sqrt n                  n            ​个段。

1. #include <bits/stdc++.h>
2. #define ll long long
3. using namespace std;
5. const int N = 5e5 + 10;
7. int n, B; char s[N];
8. int cnt = 1, last = 1, fa[N << 1], len[N << 1], ch[N << 1][26];
9. int pos[N], st[N << 1], siz[N << 1];
10. vector<int> dp[N << 1], e[N << 1];
12. int add(int w) {
13.     int now = ++cnt, p = last; last = now;
14.     len[now] = len[p] + 1;
15.     for (; p && !ch[p][w]; p = fa[p]) {
16.         ch[p][w] = now;
17.     }
18.     if (!p) {
19.         fa[now] = 1;
20.     }
21.     else {
22.         int q = ch[p][w];
23.         if (len[q] == len[p] + 1) {
24.             fa[now] = q;
25.         }
26.         else {
27.             int nw = ++cnt;
28.             len[nw] = len[p] + 1, fa[nw] = fa[q];
29.             fa[q] = fa[now] = nw;
30.             memcpy(ch[nw], ch[q], sizeof(ch[q]));
31.             for (; p && ch[p][w] == q; p = fa[p]) {
32.                 ch[p][w] = nw;
33.             }
34.         }
35.     }
36.     return now;
37. }
39. void dfs(int x) {
40.     if (len[fa[x]] + 1 <= B) {
41.         st[x] = x;
42.     }
43.     for (int y : e[x]) {
44.         st[y] = st[x];
45.         dfs(y);
46.     }
47. }
49. int main() {
50.     // freopen("in.in", "r", stdin);
51.     ios::sync_with_stdio(false);
52.     cin.tie(nullptr);
54.     cin >> n >> (s + 1);
55.     reverse(s + 1, s + n + 1);
56.     for (int i = 1; i <= n; i++) {
57.         int w = s[i] - 'a';
58.         pos[i] = add(w);
59.     }
60.     for (int i = 1; i <= n; i++) {
61.         if (i * (i + 1) / 2 > n) {
62.             break;
63.         }
64.         B = i;
65.     }
66.     for (int i = 2; i <= cnt; i++) {
67.         if (len[fa[i]] + 1 <= B) {
68.             int t = min(len[i], B) - len[fa[i]];
69.             dp[i].resize(t + 1);
70.             siz[i] = t;
71.         }
72.         e[fa[i]].push_back(i);
73.     }
74.     dfs(1);
75.     int ans = 0;
76.     for (int i = 1; i <= n; i++) {
77.         int p = st[pos[i]];
78.         int ret = 1;
79.         for (; p; p = fa[p]) {
80.             int now = len[fa[p]] + siz[p];
81.             bool flag = 0;
82.             for (int j = siz[p]; j >= 1; j--) {
83.                 if (dp[p][j] && dp[p][j] + now < i) {
84.                     ret = now + 1; flag = 1; break;
85.                 }
86.                 now--;
87.             }
88.             if (flag) {
89.                 break;
90.             }
91.         }
92.         p = st[pos[i - 1]];
93.         for (; p; p = fa[p]) {
94.             int now = len[fa[p]] + siz[p];
95.             bool flag = 0;
96.             for (int j = siz[p]; j >= 1; j--) {
97.                 if (dp[p][j] && dp[p][j] + now < i) {
98.                     ret = max(ret, now + 1); flag = 1; break;
99.                 }
100.                 now--;
101.             }
102.             if (flag) {
103.                 break;
104.             }
105.         }
106.         ans = max(ans, ret);
107.         p = st[pos[i]];
108.         for (; p; p = fa[p]) {
109.             for (int j = min(siz[p], ret - len[fa[p]]); j >= 1; j--) {
110.                 if (!dp[p][j]) {
111.                     dp[p][j] = i;
112.                 }
113.             }
114.         }
115.     }
116.     cout << ans << endl;
117. }

复制代码

细致观察了一下，发现许多可以优化的地方。
由于最后修改是把某个点往上的全部路径修改为i，因此满足单调性，而且修改的总数为                                   O                         (                         n                         )                              O(n)                  O(n)。
而且必要满足的                                   d                         p                         [                         p                         ]                         [                         j                         ]                         +                         n                         o                         w                              dp[p][j] + now                  dp[p][j]+now也有单调性，以是可以用倍增来找到点，点内开个vector存段，在点内探求的时候用二分，就能做到时间空间都是                                   O                         (                         n                         l                         o                         g                         n                         )                              O(n log n)                  O(nlogn)。

1. #include <bits/stdc++.h>
2. #define ll long long
3. using namespace std;
5. const int N = 5e5 + 10;
7. int n; char s[N];
8. int cnt = 1, last = 1, fa[N << 1], len[N << 1], ch[N << 1][26];
9. int pos[N], f[N << 1][20];
10. vector<pair<int, int>> dp[N << 1];
12. int add(int w) {
13.     int now = ++cnt, p = last; last = now;
14.     len[now] = len[p] + 1;
15.     for (; p && !ch[p][w]; p = fa[p]) {
16.         ch[p][w] = now;
17.     }
18.     if (!p) {
19.         fa[now] = 1;
20.     }
21.     else {
22.         int q = ch[p][w];
23.         if (len[q] == len[p] + 1) {
24.             fa[now] = q;
25.         }
26.         else {
27.             int nw = ++cnt;
28.             len[nw] = len[p] + 1, fa[nw] = fa[q];
29.             fa[q] = fa[now] = nw;
30.             memcpy(ch[nw], ch[q], sizeof(ch[q]));
31.             for (; p && ch[p][w] == q; p = fa[p]) {
32.                 ch[p][w] = nw;
33.             }
34.         }
35.     }
36.     return now;
37. }
39. int main() {
40.     // freopen("in.in", "r", stdin);
41.     ios::sync_with_stdio(false);
42.     cin.tie(nullptr);
44.     cin >> n >> (s + 1);
45.     reverse(s + 1, s + n + 1);
46.     for (int i = 1; i <= n; i++) {
47.         int w = s[i] - 'a';
48.         pos[i] = add(w);
49.     }
50.     for (int i = 2; i <= cnt; i++) {
51.         f[i][0] = fa[i];
52.     }
53.     for (int j = 1; j <= 19; j++) {
54.         for (int i = 1; i <= cnt; i++) {
55.             f[i][j] = f[f[i][j - 1]][j - 1];
56.         }
57.     }
58.     auto calc = [](int p, int pos) {
59.         int ret = 1;
60.         for (int j = 19; j >= 0; j--) {
61.             int q = f[p][j];
62.             if (q <= 1) continue;
63.             if (!dp[q].size() || len[fa[q]] + 1 + dp[q][0].second >= pos) {
64.                 p = q;
65.             }
66.         }
67.         if (p && (!dp[p].size() || len[fa[p]] + 1 + dp[p][0].second >= pos)) p = fa[p];
68.         int l = 0, r = (int)dp[p].size() - 1, mid, pre = -1;
69.         while (l <= r) {
70.             mid = (l + r) / 2;
71.             int minlen = mid ? dp[p][mid - 1].first + 1 : len[fa[p]] + 1;
72.             if (minlen + dp[p][mid].second < pos) {
73.                 pre = mid; l = mid + 1;
74.             }
75.             else {
76.                 r = mid - 1;
77.             }
78.         }
79.         if (pre != -1) {
80.             ret = max(ret, min(pos - 1 - dp[p][pre].second, dp[p][pre].first) + 1);
81.         }
82.         return ret;
83.     };
84.     int ans = 1;
85.     for (int i = 1; i <= n; i++) {
86.         int ret = max(calc(pos[i], i), calc(pos[i - 1], i));
87.         ans = max(ans, ret);
88.         int p = pos[i];
89.         for (int j = 19; j >= 0; j--) {
90.             int q = f[p][j];
91.             if (q > 1 && len[fa[q]] + 1 > ret) {
92.                 p = q;
93.             }
94.         }
95.         if (p > 1 && len[fa[p]] + 1 > ret) p = fa[p];
96.         while (p > 1) {
97.             pair<int, int> now = {min(ret, len[p]), i};
98.             int last = !dp[p].size() ? len[fa[p]] : dp[p][(int)dp[p].size() - 1].first;
99.             if (last < now.first) {
100.                 dp[p].push_back(now);
101.                 p = fa[p];
102.             }
103.             else {
104.                 break;
105.             }
106.         }
107.     }
108.     cout << ans << endl;
109. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。