当前位置:首页 > 开发 > Web前端 > Ext > 正文

POJ 1961 Period KMP算法之next数组的应用

发表于: 2015-11-13   作者:互联网   来源:转载   浏览:
ext
摘要: 题意:给一个长度为n的字符串,如果它长度为l(2 <= l <= n)的前缀部分是由一些相同的字符串相接而成,输出前缀的长度l和长度为l时字符串重复的最大次数。 例如字符串为: aaaba。对于长度为2的前缀"aa"来说, “aa”最多由两个‘a’连接而成。对于长度为3的前缀"aaa"来说,“aaa”最多由三个'a'连接而成。 思路:该问题恰

题意:给一个长度为n的字符串,如果它长度为l(2 <= l <= n)的前缀部分是由一些相同的字符串相接而成,输出前缀的长度l和长度为l时字符串重复的最大次数。

例如字符串为: aaaba。对于长度为2的前缀"aa"来说, “aa”最多由两个‘a’连接而成。对于长度为3的前缀"aaa"来说,“aaa”最多由三个'a'连接而成。

思路:该问题恰好用到了next数组的特性。

在kmp算法中,当字符串匹配失败时,next数组给出模式串接下来要匹配的位置。它的目的在于尽可能得利用模式串的特征少往回退。

假如匹配失败的位置为j,则对于S[0]S[1]S[2]...S[j-1]都是匹配成功的。现如果有一个最大的k,且满足S[0]S[1]S[2]...S[k-1]与S[j-k]S[j-k+1]...S[j-1]相同,则可知接下来应当将模式串的S[k]与主串匹配,即next[j] = k。

考虑该题情况,如果长度为l的前缀是由字符串重复构成的,则next[l] != 0(由上面k的定义可知),且此时构成前缀的重复子串的最小长度为l - next[l],l % (l - next[l]) = 0,最大重复次数为l / (l - next[l])。

 

 1 #include<stdio.h>

 2 #define maxn 1000010

 3 char str[maxn];

 4 int next[maxn], len;

 5 void get_next()

 6 {

 7     next[0] = -1;

 8     int i = 0;

 9     int j = -1;

10     while (i < len)

11     {

12         if (j == -1 || str[i] == str[j])

13         {

14             i++; j++;

15             next[i] = j;

16         }

17         else j = next[j];

18     }

19 }

20 int main()

21 {

22     int cas = 1;

23     while (scanf("%d", &len) && len)

24     {

25         scanf("%s", str);

26         get_next();

27         printf("Test case #%d\n", cas++);

28         for (int i = 2; i <= len; i++)

29             if (next[i] && i % (i - next[i]) == 0)

30                 printf("%d %d\n", i, i / (i - next[i]));

31         printf("\n");

32     }

33     return 0;

34 }

 

 

 

POJ 1961 Period KMP算法之next数组的应用

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号