首页 > 其他 > 详细

BZOJ3620(kmp)

时间:2019-04-27 21:10:57      阅读:180      评论:0      收藏:0      [点我收藏+]

要点

  • 本题使用\(O(n^2)\)的算法
  • 外层枚举左端点,内层一直kmp到结尾,中间遇到合法的就ans++
  • 如果是acccca这种数据直接kmp过程顺手判断即可;但是aaa这种数据,j = 2,实际判断是不合法的,也就是说,其实只要Next里有合法的即本串合法,因此多开Num数组记录
#include <cstdio>
#include <cstring>
#define min(a, b) a > b ? b : a

const int maxn = 15e3 + 5, INF = 0x3f3f3f3f;
int k, Next[maxn], Num[maxn], ans;
char str[maxn];

int main() {
    scanf("%s %d", str + 1, &k);
    int n = strlen(str + 1);

    for (int l = 1; l <= n; l++) {
        memset(Num, 0x3f, sizeof Num);
        Next[1] = 0;
        for (int len = 2, j = 0; len <= n - l + 1; len++) {
            int r = l + len - 1;
            while (j && str[r] != str[l + j])   j = Next[j];
            if (str[r] == str[l + j])   j++;
            Next[len] = j;
            if (j < k)  Num[len] = INF;
            else    Num[len] = min(Num[Next[len]], j);
            if (Num[len] * 2 < len) ans++;
        }
    }

    printf("%d\n", ans);
    return 0;
}

BZOJ3620(kmp)

原文:https://www.cnblogs.com/AlphaWA/p/10780328.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!