【XJTUOJ 1058】JM的荧光棒工厂

【XJTUOJ 1058】JM的荧光棒工厂

题目描述

黑心商人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]);
    }
}