字符串专题训练赛03解题报告

CF985F-Isomorphic Strings

描述

给定一个字符串\(s\),执行\(m\)次询问,每次询问判断\(s\)的两个子串是否同构。对于两个字符串同构的定义可以概括为:如果\(s\)中的字符可以被替换得到\(t\),那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。

题解

一开始做这道题首先想到的是用两个map去完成。从前向后遍历字符串,如果是首次出现一个字母,就记录这个字母和对应位置上另一个字符串的字母,如果不是首次出现,就去判断这个字母对应的字母和存的字母是否相同。对于两个字符串各做一遍上述操作,如果没有产生矛盾,就判断为同构,否则不同同构。根据数据范围,考虑最糟糕的情况是\(m\)次询问全部是针对\(s\)整个串,最终最坏复杂度为\(O(nm)\),最终会TLE。

那么考虑正解,个人感觉这道题的正解从位运算绕一下理解更方便。首先,\(s\)只由26个小写英文字母组成,其次,我们只需要判断是否同构而不需要知道对于每次判断而言字母之间的映射关系。基于这两点,我们考虑这样一个做法:

对于26个字母,构造26个01串,对于每个字母,遍历\(s\),如果\(s[i]\)与该字母相同则为1,否则为0。而后,我们可以将这26个字符串转换成十进制的数。对于判断同构串时,构造的两组01串转化后,如果存在两个数对应相等,那么说明这两个数代表的字母的对应位置在两串中完全一致,也就是符合同构的条件。那么,我们只需要判断两组数是否完全相等就可以了。

但是,此时考虑到两组01串每个长度可以长达\(2 \times 10^5\),所以转换成十进制的数存不下,所以我们想到可以直接利用哈希去判断两组01串是否相等。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;
const ll mod = 1e9 + 7, B = 233;
ll h[26][N], p[N] = {1ll};
char S[N];
int main()
{
int n, m, x, y, l;
scanf("%d%d", &n, &m);
getchar();
scanf("%s", S + 1);
for (int i = 1; i <= n; i++)
p[i] = p[i - 1] * B % mod;
for (int i = 0; i < 26; i++)
{
for (int j = 1; j <= n; j++)
{
h[i][j] = (h[i][j - 1] * B + (long long)(S[j] == i + 'a')) % mod;
}
}
while (m--)
{
scanf("%d%d%d", &x, &y, &l);
vector<int> v1, v2;
for (int i = 0; i < 26; ++i)
{
v1.push_back(((h[i][x + l - 1] - p[l] * h[i][x - 1]) % mod + mod) % mod);
v2.push_back(((h[i][y + l - 1] - p[l] * h[i][y - 1]) % mod + mod) % mod);
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
printf("%s\n", v1 == v2 ? "YES" : "NO");
}
}

CF961F-k-substrings

描述

给定一个字符串\(s\),每次从左右两端去除一个字母,构造出\(\lceil \frac {|s|} 2 \rceil\)个子串,对于每个子串,求解它的最长公共前后缀的长度。

题解

如果是构造完了去求解最长公共前后缀的长度,复杂度是\(O(n^2)\),会TLE。但是考虑这个暴力的做法中,每次求解的时候会有额外信息提供,所以考虑递推的思想。

设答案序列为\(ans[1...{\lceil \frac {|s|} 2 \rceil}]\),考虑\(ans[i+1]\)\(i+1\)相较于\(i\)号子串,左右两端各少一个字母,所以即使\(i+1\)号子串前缀加后缀就是这个子串本身,\(ans[i+1]\)相较于\(ans[i]\)也至少小2。

根据这样的规律,我们可以倒着去做,从中间开始计算,每次向两边扩展一个字母,枚举\(ans[i+1]+2,ans[i+1], ans[i+1]-2,...,-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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
const ll B = 233, mod = 1e9 + 7;
char s[N];
int n, cnt, l, r, ans[N];
ll h[N], p[N] = {1ll};
ll gethash(int l, int r)
{
return ((h[r] - h[l - 1] * p[r - l + 1]) % mod + mod) % mod;
}
int main()
{
scanf("%d", &n);
getchar();
scanf("%s", s + 1);
for (int i = 1; i <= n; i++)
{
p[i] = p[i - 1] * B % mod;
h[i] = (h[i - 1] * B % mod + s[i]) % mod;
}
cnt = n + 1 >> 1;
if (n & 1)
ans[cnt] = -1, l = r = cnt;
else
{
l = cnt, r = cnt + 1;
if(s[l] == s[r]) ans[cnt] = 1;
else ans[cnt] = -1;
}
for(int i = cnt - 1; i > 0; i--)
{
l--, r++;
for(int j = ans[i + 1] + 2; j >= -1; j -= 2)
{
if(j == -1 || gethash(l, l + j - 1) == gethash(r - j + 1, r))
{
ans[i] = j;
break;
}
}
}

for(int i = 1; i <= cnt; i++) printf("%d ", ans[i]);
return 0;
}
----- 本文结束 感谢阅读 -----
0%