文章目录
  1. 1. 题目描述
  2. 2. 输入格式
  3. 3. 输出格式
  4. 4. 样例一
    1. 4.1. input
    2. 4.2. output
    3. 4.3. explanation
  5. 5. 样例二
  6. 6. 样例三
  7. 7. 限制与约定
  8. 8. codes

题目描述

如果一个字符串可以被拆分为 $AABB$ 的形式,其中 $A$ 和 $B$ 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。

例如,对于字符串 aabaabaa,如果令 $A = \mathrm{aab}$,$B = \mathrm{a}$,我们就找到了这个字符串拆分成 $AABB$ 的一种方式。

一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 $A=\mathrm{a}$,$B=\mathrm{baa}$,也可以用 $AABB$ 表示出上述字符串;但是,字符串 abaabaa 就没有优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意:

  1. 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
  2. 在一个拆分中,允许出现 $A=B$。例如 cccc 存在拆分 $A=B=\mathtt{c}$。
  3. 字符串本身也是它的一个子串。

输入格式

每个输入文件包含多组数据。输入文件的第一行只有一个整数 $T$,表示数据的组数。保证 $1 \le T \le 10$。

接下来 $T$ 行,每行包含一个仅由英文小写字母构成的字符串 $S$,意义如题所述。

输出格式

输出 $T$ 行,每行包含一个整数,表示字符串 $S$ 所有子串的所有拆分中,总共有多少个是优秀的拆分。

样例一

input

 4 aabbbb cccccc aabaabaabaa bbaabaababaaba  

output

 3 5 4 7  

explanation

我们用 $S[i, j]$ 表示字符串 $S$ 第 $i$ 个字符到第 $j$ 个字符的子串(从 $1$ 开始计数)。

第一组数据中,共有 $3$ 个子串存在优秀的拆分:

$S[1,4] = \mathtt{aabb}$,优秀的拆分为 $A=\mathtt{a}$,$B = \mathtt{b}$;

$S[3,6] = \mathtt{bbbb}$,优秀的拆分为 $A=\mathtt{b}$,$B = \mathtt{b}$;

$S[1,6] = \mathtt{aabbbb}$,优秀的拆分为 $A= \mathtt{a}$,$B = \mathtt{bb}$。

而剩下的子串不存在优秀的拆分,所以第一组数据的答案是 $3$。

第二组数据中,有两类,总共 $4$ 个子串存在优秀的拆分:

对于子串 $S[1,4] = S[2,5] = S[3,6] = \mathrm{cccc}$,它们优秀的拆分相同,均为 $A = \mathrm{c}$,$B = \mathrm{c}$,但由于这些子串位置不同,因此要计算 $3$ 次;

对于子串 $S[1,6] = \mathrm{cccccc}$,它优秀的拆分有 $2$ 种:$A = \mathrm{c}$,$B = \mathrm{cc}$ 和 $A = \mathrm{cc}$,$B = \mathrm{c}$,它们是相同子串的不同拆分,也都要计入答案。

所以第二组数据的答案是 $3 + 2 = 5$。

第三组数据中,$S[1,8]$ 和 $S[4,11]$ 各有 $2$ 种优秀的拆分,其中 $S[1,8]$ 是问题描述中的例子,所以答案是 $2 + 2 = 4$。

第四组数据中,$S[1,4]$,$S[6,11]$,$S[7,12]$,$S[2,11]$,$S[1,8]$ 各有 $1$ 种优秀的拆分,$S[3,14]$ 有 $2$ 种优秀的拆分,所以答案是 $5 + 2 = 7$。

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

对于全部的测试点,保证 $1 \le T \le 10$。以下对数据的限制均是对于单组输入数据而言的,也就是说同一个测试点下的 $T$ 组数据均满足限制条件。

我们假定 $n$ 为字符串 $S$ 的长度,每个测试点的详细数据范围见下表:

测试点编号 $n$ 其他约束
1、2$\leq 300$$S$中所有字符全部相同
3、4$\leq 2000$
5、6$\leq 10$
7、8$\leq 20$
9、10$\leq 30$
11、12$\leq 50$
13、14$\leq 100$
15$\leq 200$
16$\leq 300$
17$\leq 500$
18$\leq 1000$
19$\leq 2000$
20$\leq 30000$

时间限制:$1.5\texttt{s}$

空间限制:$512\texttt{MB}$

codes

哈希暴力95分。送的分有些多啊,虽然我很弱,敲了好久。:(

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=30010;
const int base=666233;
const int mod1=1000000007;
const int mod2=1000000009;
int T;
char str[maxn];
int len;
int f1[maxn], f2[maxn];
int hf1[maxn], hf2[maxn];
int hb1[maxn], hb2[maxn];
ll ans;
int main()
{
hb1[0]=1;
hb2[0]=1;
for(int i=1; i<30005; i++)
{
hb1[i]=(ll)hb1[i-1]*base %mod1;
hb2[i]=(ll)hb2[i-1]*base %mod2;
}
scanf("%d", &T);
while(T--)
{
ans=0;
memset(hf1, 0, sizeof(hf1));
memset(hf2, 0, sizeof(hf2));
memset(f1, 0, sizeof(f1));
memset(f2, 0, sizeof(f2));
scanf("%s", str);
len=strlen(str);
hf1[0]=0;
hf2[0]=0;
for(int i=0; i<len; i++)
{
hf1[i+1]=((ll)hf1[i]*base +str[i]) %mod1;
hf2[i+1]=((ll)hf2[i]*base +str[i]) %mod2;
}
for(int i=1; i<=len; i++)
{
//printf("%d %d\n", hf1[i], hf2[i]);
for(int j=1; i-j-j>=0; j++)
{
int t11, t12, t21, t22;
t11= (hf1[i]+mod1-(ll)hf1[i-j]*hb1[j]%mod1) %mod1;
t12= (hf2[i]+mod2-(ll)hf2[i-j]*hb2[j]%mod2) %mod2;
t21= (hf1[i-j]+mod1-(ll)hf1[i-j-j]*hb1[j]%mod1) %mod1;
t22= (hf2[i-j]+mod2-(ll)hf2[i-j-j]*hb2[j]%mod2) %mod2;
if(t11=t21 && t12==t22)
f1[i]++;
}
for(int j=1; i+j+j<=len; j++)
{
int t11, t12, t21, t22;
t11= (hf1[i+j]+mod1-(ll)hf1[i]*hb1[j]%mod1) %mod1;
t12= (hf2[i+j]+mod2-(ll)hf2[i]*hb2[j]%mod2) %mod2;
t21= (hf1[i+j+j]+mod1-(ll)hf1[i+j]*hb1[j]%mod1) %mod1;
t22= (hf2[i+j+j]+mod2-(ll)hf2[i+j]*hb2[j]%mod2) %mod2;
if(t11==t21 && t12==t22)
f2[i]++;
}
}
for(int i=1; i<=len; i++)
{
//printf("%d %d\n", f1[i], f2[i]);
ans+=(ll)f1[i]*f2[i];
}
printf("%lld\n", ans);
}
return 0;
}

文章目录
  1. 1. 题目描述
  2. 2. 输入格式
  3. 3. 输出格式
  4. 4. 样例一
    1. 4.1. input
    2. 4.2. output
    3. 4.3. explanation
  5. 5. 样例二
  6. 6. 样例三
  7. 7. 限制与约定
  8. 8. codes