题目描述：
给出一个长度为 $n$ 的字符串，将其分成 $k$ 个非空子字符串，并且满足这 $k$ 个字符串元组回文对应相等。比如(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)
数据范围：
$1\le n \le 1000$
题解：
数据范围比较小，可以直接暴力。贪心的每次去掉两侧最短的相等的字符串，判断字符串是否相等可以直接暴力判断。每次能给答案贡献 $2$ ，如果最后字符串不为空则需要对答案加 $1$ 。
滚动hash：
滚动hash类似使用前缀和。使用 $hash[l,r] = hash[0, r] - hash[0, l - 1]$ 来计算子区间的 $hash$ 值。 $hash$ 是使用迭代乘 $base$ 实现的，也就是以 $base$ 为进制计算出来的一个数。 $hash(abc) = a\times base^2 + b\times base^1 + c \times base^0$ ， $hash(bc) = b \times base^1 + c \times base^0$ .因此可以得到 $hash[l,r] = hash[0,r] - hash[0,l-1] * base^{r - l + 1}$ 。需要乘以 $base^{r - l + 1}$ ，因为 $hash[0,r]$ 是在 $hash[0,l-1]$ 的基础之上又加入了 $r - l + 1$ 个字符，每次乘以一个 $base$ 。
使用一个 $pow$ 数组用来计算 $base$ 的次幂，其中 $pow[i] = base^i$ 。同时前缀和由于需要 $l-1$ ，会出现负值。因此需要调整为 $hash[1,n]$ 表示 $hash$ 值。
哈希 $base$ 取值：13,131,1331等。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
static void optimize_cpp_stdio() { ios::sync_with_stdio(false), cin.tie(0); }
bool greedy(int &l, int &r, string &s)
{
int size = r - l + 1;
for (int k = 1; k <= size / 2; ++k)
{
bool same = true;
for (int i = 0; i < k; ++i)
{
if (s[l + i] != s[r - k + 1 + i])
{
same = false;
break;
}
}
if (same)
{
l = l + k;
r = r - k;
return true;
}
}
return false;
}
int longestDecomposition(string text)
{
int l = 0, r = text.size() - 1;
int ans = 0;
while (l <= r)
{
if (greedy(l, r, text))
{
ans += 2;
}
else
break;
}
if (l > r)
return ans;
else
return ans + 1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| class Solution
{
public:
#ifndef ll
using ll = long long;
#endif
const static int maxn = 1e3 + 1;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
const static long long mod = 1e9 + 7;
const static int base = 131;
static void optimize_cpp_stdio() { ios::sync_with_stdio(false), cin.tie(0); }
ll hash[maxn], pow[maxn];
void init(string &s, int n)
{
pow[0] = 1;
for (int i = 0; i < n; ++i)
{
pow[i + 1] = pow[i] * base % mod;
hash[i + 1] = (hash[i] * base + (s[i] - '0')) % mod;
}
}
ll get_hash(int l, int r)
{
return (hash[r + 1] - hash[l] * pow[r - l + 1] % mod + mod) % mod;
}
bool greedy(int &l, int &r, string &s)
{
int size = r - l + 1;
for (int k = 1; k <= size / 2; ++k)
{
if (get_hash(l, l + k - 1) == get_hash(r - k + 1, r))
{
l += k;
r -= k;
return true;
}
}
return false;
}
int longestDecomposition(string text)
{
optimize_cpp_stdio();
int l = 0, r = text.size() - 1;
init(text, r + 1);
int ans = 0;
while (l <= r)
{
if (greedy(l, r, text))
{
ans += 2;
}
else
break;
}
if (l > r)
return ans;
else
return ans + 1;
}
};
|