题意：
给一个字符串 将这个字符串从每个字符为起点的串分类输出 例如abab 它的串分别为abab baba abab baba 于是输出两种 abab的两个串起点分别是0、2，baba的是1、3。
解法：
首先我们可以观察到，每个串的长度都是相同的。我们只要找到这个字符串的最大循环节长度maxlen，就可以知道有maxlen种串，然后按照循环直接输出每种串的每个位置。
这个时候很多人用了kmp，但是这个题其实是可以用更简单的方式来找出这个循环节。最大循环节长度maxlen显然必须可以被字符串长度len整除，所以必然是len的因子，而字符串的因子个数小于50，所以我们可以直接暴力枚举len的每个因子，验证最大循环节。时间复杂度小于50*len。
以下为队友的代码
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int MAXN = 1000005;
#define INF 0X3f3f3f3f
int n, m;
int a;
char s[MAXN];
int main()
{
int T;
while (scanf("%s", s) != EOF)
{
int l = strlen(s);
int t = 0;
for (int i = 1; i <= l; i++)
{
if (l % i == 0)
{
int flag = 0;
for (int j = 0; j < i; j++)
{
for (int k = 1; k <= l / i - 1; k++)
{
if (s[j] != s[j + k * i])
{
flag = 1;
break;
}
}
}
if (flag == 0)
{
t = i;
break;
}
}
}
printf("%d\n", t);
for (int i = 0; i < t; i++)
{
printf("%d", l/t);
for (int j = 0; j < l/t; j++)
{
printf(" %d", i + t * j);
}
printf("\n");
}
}
} 
全部评论
(0) 回帖