KMP-(HDU1358)Period[前缀中的周期]

矫情吗；* 2022-05-17 01:50 274阅读 0赞

  • KMP-(HDU1358)Period

  • 题目链接：9:前缀中的周期

  • KMP基础：

给个传送门复习下KMP：串的模式匹配算法-KMP算法

  • 思路：

给定Next[i]，Next[i]指向的总是上一循环节后面的一个字符，所以上一循环节末尾为Next[i]-1

当前循环节的末尾为i-1，易得当前循环节长度：（i-1）-（Next[i]-1）=i-Next[i]

由题意已经假设0~i-1的串是循环的，所以要判断循环是否成立，只要满足长度 i 是当前循环节长度的倍数

即：i%（Next[i]-1）==0，同时必须在Next[i]！=0 前提下（不重复的串Next数组中很多0）

  • 总结：

对于Next数组，满足 i % ( i - Next[i] ) == 0 && Next[i] != 0说明找到当前循环节

循环节长度：**i-Next[i]**

循环次数：i/(i-Next[i])

  • 代码：

    include

    include

    using namespace std;
    //HDU1358 Period

    define MAXSIZE 1000005

    int Next[MAXSIZE];
    char Str[MAXSIZE];
    int Len;

    void KMP()
    {

    1. int j = -1, k = 0;
    2. Next[0] = -1;
    3. while (k < Len)
    4. {
    5.     if (j == -1 || Str[j] == Str[k])
    6.     {
    7.         j++;
    8.         k++;
    9.         Next[k] = j;    //j==Next[k]
    10.         if (k % (k - j) == 0 && j != 0)
    11.         {
    12.             cout << k << " " << k / (k - j) << endl;
    13.         }
    14.     }
    15.     else
    16.         j = Next[j];
    17. }

    }

    int main()
    {

    1. int Case = 0;
    2. while (cin >> Len && Len)
    3. {
    5.     cin >> Str;
    6.     cout << "Test case #" << ++Case << endl;
    7.     KMP();
    8.     cout << endl;
    9. }
    10. return 0;

    }

  • 参考：

Jack Ge for ACM- KMP算法 —— next 数组的应用 —- 前缀中最小循环节，最大重复次数

他山之石，我之师，共勉

发表评论

表情：
评论列表 （有 0 条评论，274人围观）

还没有评论，来说两句吧...

相关阅读