题目描述
黑心商人JM雇佣了10000个wzk来生产魔法荧光棒,这种魔法荧光棒拿在dalao的手上就会闪闪发光。精通字符串理论的wzk在工作的时候突发奇想:如果这些荧光棒可以一根接一根地绑在一起,那该有多好!
被批量生产的荧光棒可以视为一个仅包含小写字母的字符串 $s$ ,没错这些荧光棒都是一模一样的。两个荧光棒可以被绑在一起,那么他们必须在被绑处有公共的部分,这个部分的长度叫作损失长度。
例如对于 $s = $ abcccab ,他可以以 $L = 2$ 的损失长度绑在一起,就像这样:
abcccab
abcccab
例如对于 $s = $ aacaa ,他可以以 $L = 1$ 或 $L = 2$ 的损失长度绑在一起,就像这样:
aacaa
aacaa
or:
aacaa
aacaa
当然你不能这样绑,因为这毫无意义,绑了跟没绑一样:
aacaa
aacaa
现在wzk随意地制造了一种荧光棒,他想知道有多少种不同的非零的损失长度,使得两根荧光棒可以被绑在一起。损失长度必须小于荧光棒的总长。
Solution
大水题。简化一下题意,显然题目是叫我们找出每一对相等的前缀与后缀。所以只需要遍历每一对前缀与后缀比较就行了。
样例输入1
aacaa
样例输出1
2
1 2
AC Code
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
typedef long long llint;
const bool DEBUG_ENABLE = 0;
const int MAXN = 2e5 + 5;
const int MOD = 19260827;
int main() {
/*==================================*/
#ifdef LOCAL_JUDGE
freopen("../in.in", "r", stdin);
freopen("../out.out", "w", stdout);
#endif
/*==================================*/
char str[MAXN];
std::vector<int> a;
scanf("%s", str);
int n = strlen(str), cnt = 0;
for(int i = 1; i < n; ++i) {
if(!memcmp(str, str + n - i, i)) { //比strcmp快很多
a.push_back(i);
cnt++;
}
}
printf("%d\n", cnt);
for(int i = 0; i < a.size(); ++i) {
printf("%d ", a[i]);
}
}