AcWing 141. 周期

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 141. 周期原题链接简单

作者：

秦淮岸灯火阑珊 , 2019-01-31 18:37:03 , 所有人可见 , 阅读 4764

21

4

题目描述

一个字符串的前缀是从第一个字符开始的连续若干个字符，例如”abaab”共有5个前缀，分别是a, ab, aba, abaa, abaab。

我们希望知道一个N位字符串S的前缀是否具有循环节。

换言之，对于每一个从头开始的长度为 i （i>1）的前缀，是否由重复出现的子串A组成，即 AAA…A （A重复出现K次,K>1）。

如果存在，请找出最短的循环节对应的K值（也就是这个前缀串的所有可能重复节中，最大的K值）。

输入格式
输入包括多组测试数据，每组测试数据包括两行。

第一行输入字符串S的长度N。

第二行输入字符串S。

输入数据以只包括一个0的行作为结尾。

输出格式
对于每组测试数据，第一行输出 “Test case #” 和测试数据的编号。

接下来的每一行，输出具有循环节的前缀的长度i和其对应K，中间用一个空格隔开。

前缀长度需要升序排列。

在每组测试数据的最后输出一个空行。

数据范围
$2≤N≤1000000$

样例

输入样例：
3
aaa
4
abcd
12
aabaabaabaab
0
输出样例：
Test case #1
2 2
3 3

Test case #2

Test case #3
2 2
6 2
9 3
12 4

KMP匹配+性质求解

首先发现一个性质,对字符串S自己匹配求出next数组,然后根据定义,对于每一个i,s[i-next[i]+1~i]与s[1~next[i]]是相等的,而且不存在更大的next值满足条件.具体证明可以看李煜东金牌爷的<<算法竞赛进阶指南>>

既然如此的话,那么我们发现当i-next[i]能够整除i时候,那么s[1~i-next[i]]就是s[i-1]的最小循环元,至于次数那么也就是i/(i-next[i]).

C++ 代码

#include <cstdio>//如果你的数组名为Next,那么请不要用algorithm库和bits库
using namespace std;
const int N=1e6+10;
int next[N],n,m,i,j,len,cnt;
char a[N];
void calc_next()//求后缀数组
{
    next[1]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j>0 && a[i]!=a[j+1])
            j=next[j];
        if (a[j+1]==a[i])
            j++;
        next[i]=j;
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF && n)
    {
        scanf("%s\n",a+1);
        printf("Test case #%d\n",++cnt);
        calc_next();
        for(int i=2;i<=n;i++)
            if (i%(i-next[i])==0 && i/(i-next[i])>1)//满足条件
                printf("%d %d\n",i,i/(i-next[i]));
        puts("");
    }
    return 0;
}

10 评论

rongyi 5个月前

给喜欢0index作个参考

#include <iostream>
#include <vector>

using namespace std;

string s;
int n = 0;

vector<int> genlps(string &s) {
  int sz = s.size();
  vector<int> lps(sz, 0);

  for (int i = 1, j = 0; i < sz; i++) {
    while (j > 0 && s[j] != s[i]) {
      // fallback
      j = lps[j - 1];
    }
    if (s[i] == s[j]) {
      lps[i] = ++j;
    }
  }

  return lps;
}

int main() {
  ios::sync_with_stdio(false);

  int round = 1;
  while (true) {
    cin >> n;
    if (n == 0) {
      break;
    }
    cin >> s;
    auto lps = genlps(s);

    cout << "Test case #" << round++ << endl;
    for (int i = 1; i < s.size(); i++) {
      auto len = i + 1;
      if ((len % (len - lps[i]) == 0) && len / (len - lps[i]) > 1) {
        cout << len << " " << len / (len - lps[i]) << endl;
      }
    }
    cout << endl;
  }

  return 0;
}