#P2534. Uva10829L-gap字符串

    ID: 1586 传统题 1000ms 128MiB 尝试: 424 已通过: 113 难度: 8 上传者: 标签>CF2400提高+/省选-后缀数组LCP+RMQST 表Kasai 算法倍增计数排序贡献法鸣谢刘汝佳先生授权使用

Uva10829L-gap字符串

题目描述

有一种形如 uvuuvu 形式的字符串,其中 uu 是非空字符串,且 vv 的长度正好为 LL,那么称这个字符串为 LL-Gap 字符串。

给出一个字符串 SS 以及一个正整数 LL,问 SS 中有多少个 LL-Gap 子串。

输入格式

第一行一个整数 LL,第二行一个字符串 SS。

输出格式

一个数表示 SS 中有多少个 LL-Gap 子串。

3
aabbaa
2

数据范围

SS 的长度不超过 5×1045\times 10^4,L≤10L\leq 10。

来源

鸣谢刘汝佳先生授权使用。