[题目][蓝桥杯ALGO-88] 字符统计

一、题目

1、题目链接

http://lx.lanqiao.cn/problem.page?gpid=T220（需要登录且需要 VIP 账户）

1、问题描述

给定一个长度为 n 的字符串 S，还有一个数字 L，统计长度大于等于 L 的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。

2、输入格式

第一行一个数字L。

第二行是字符串S。

3、输出格式

一行，题目要求的字符串。

4、样例输入

bbaabbaaaaa

5、样例输出

bbaa

6、数据范围

n <= 60，L大于0，且不超过S的长度。

二、分析与思路

本来是一道大水题，但突然想把所有可以的思路都列出来一下，而且水的原因主要是数据范围很小，调大了自然需要更优的算法。

1、O(n ^ 4) 纯暴力枚举

先枚举子串长度，再枚举子串起始位置，再枚举该位置之后的子串的起始位置，并逐位进行比较，总共需要 4 重 for 循环，即 O(n ^ 4) 的时间复杂度，无需过多分析。

2、O(n ^ 3) 暴力枚举 + KMP

在纯暴力枚举的基础上优化，枚举完子串起始位置后，对于每一个子串采用 KMP 算法判断相同子串的个数，时间复杂度为 O(n ^ 3)。

3、O(n ^ 3) 动态规划

设 f[i][j][k] 表示 “长度为 i，起始位置分别为 j 和 k 的两个子串是否相等”，相等为 1，反之为 0。

4、O(n ^ 2 log n) 字符串 Hash

记录所有子串的 Hash 值，并记录每个 Hash 值出现的次数。

时间复杂度肯定是很优的，但这道题还需要判断长度和起始位置以满足要求，需要开一个类来保存。

另外代码中并没有记录每个 Hash 值的出现次数，而是将所有值排序，直接判断连续相同的数的个数，省去了用 map 映射 Hash 值。

5、O(n ^ 2) 后缀数组

暂略

三、代码

代码 1（纯暴力枚举）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 60 + 5;
 5 
 6 int l, la, ansl, nob, tot, mx;
 7 char a[MAXN], b[MAXN], ans[MAXN];
 8 
 9 int main() {
10     cin >> l >> a + 1, la = strlen(a + 1);
11     for (int i = la; i >= l; i--)
12         for (int j = 1; j <= la - i + 1; j++) {
13             tot = 0;
14             memset(b, 0, sizeof(b));
15             for (int k = j; k <= j + i - 1; k++)
16                 b[k - j + 1] = a[k];
17             for (int k = 1; k <= la - i + 1; k++) {
18                 nob = 0;
19                 for (int o = k; o <= k + i - 1; o++)
20                     if (a[o] != b[o - k + 1]) {
21                         nob = 1;
22                         break;
23                     }
24                 tot += (!nob);
25             }
26             if (tot > mx) {
27                 mx = tot;
28                 for (int k = 1; k <= i; k++)
29                     ans[k] = b[k];
30                 ansl = i; 
31             }
32         }
33     for (int i = 1; i <= ansl; i++)
34         cout << ans[i];
35     return 0;
36 }

代码 2（暴力枚举 + KMP）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 60 + 5;

int l, la, ansl, nob, tot, mx, f[MAXN];
char a[MAXN], b[MAXN], ans[MAXN];

int main() {
    cin >> l >> a + 1, la = strlen(a + 1);
    for (int i = la; i >= l; i--)
        for (int j = 1; j <= la - i + 1; j++) {
            tot = 0;
            memset(b, 0, sizeof(b));
            for (int k = j; k <= j + i - 1; k++)
                b[k - j + 1] = a[k];
            memset(f, 0, sizeof(f));
            f[0] = -1;
            for (int k = 1, x = -1; k <= i; k++) {
                while (x >= 0 && b[x + 1] != b[k]) x = f[x];
                f[k] = ++x;
            }
            for (int k = 1, x = 0; k <= la; k++) {
                while (x >= 0 && b[x + 1] != a[k]) x = f[x];
                tot += (++x == i);
            }
            if (tot > mx) {
                mx = tot;
                for (int k = 1; k <= i; k++)
                    ans[k] = b[k];
                ansl = i; 
            }
        }
    for (int i = 1; i <= ansl; i++)
        cout << ans[i];
    return 0;
}

代码 3（动态规划）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 60 + 5;
 5 
 6 int l, la, ansl, mx, f[MAXN][MAXN][MAXN];
 7 char a[MAXN], ans[MAXN];
 8 
 9 int main() {
10     cin >> l >> a + 1, la = strlen(a + 1);
11     for (int i = 1; i <= la; i++)
12         for (int j = 1; j <= la; j++)
13             f[0][i][j] = 1;
14     for (int i = 1; i <= la; i++)
15         for (int j = 1; j <= la - i + 1; j++) {
16             int o = 0;
17             for (int k = j + 1; k <= la - i + 1; k++)
18                 if (f[i - 1][j][k] && a[j + i - 1] == a[k + i - 1])
19                     f[i][j][k] = 1, o++;
20             if (o > mx && i >= l || o == mx && i > ansl) {
21                 mx = o, ansl = i;
22                 for (int k = 1; k <= i; k++)
23                     ans[k] = a[j + k - 1];
24             }
25         }
26     for (int i = 1; i <= ansl; i++)
27         cout << ans[i];
28     return 0;
29 }

代码 4（字符串 Hash）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 
 6 const ll MOD = 1e9 + 7;
 7 const ll MAXN = 60 + 5;
 8 const ll INF = 1 << 30;
 9 const ll x = 131;
10 
11 ll l, la, ansl, tot, cnt, mx, anss = INF, fir;
12 char a[MAXN], ans[MAXN];
13 
14 class Data {
15 public:
16     ll v, l, s;
17     bool operator < (const Data& o) const {
18         return v < o.v;
19     }
20 } d[MAXN * MAXN];
21 
22 int main() {
23     cin >> l >> a + 1, la = strlen(a + 1);
24     for (int i = 1; i <= la; i++) {
25         ll o = 0;
26         for (int j = i; j <= la; j++) {
27             o = (o * x + a[j]) % MOD;
28             if (j - i + 1 >= l)
29                 d[++tot] = (Data) {o, j - i + 1, i};
30         }
31     }
32     sort(d + 1, d + tot + 1);
33     for (int i = 1; i <= tot; i++)
34         if (d[i].v == d[i - 1].v) fir = min(fir, d[i - 1].s), cnt++;
35         else {
36             fir = min(fir, d[i - 1].s);
37             if (cnt > mx || cnt == mx && d[i - 1].l > ansl || 
38                 cnt == mx && d[i - 1].l == ansl && fir < anss)
39                 mx = cnt, ansl = d[i - 1].l, anss = fir;
40             cnt = 1, fir = INF;
41         }
42     for (int i = 1; i <= ansl; i++)
43         cout << a[anss + i - 1];
44     return 0;
45 }

四、相关知识点

5.2 字符串 Hash

5.3 KMP / 扩展 KMP 算法

5.5 后缀数组 SA / 后缀自动机 SAM / 后缀树

4.1 记忆化搜索与动态规划