[bzoj3670][2014湖北省队互测week2]似乎在梦中见过的样子
2024-10-10 11:26:42
Description
已知一个字符串S,求它有多少个形如A+B+A的子串(len(A)>=k,len(B)>=1 )。
Input
第一行一个字符串,第二行一个数 k。
Output
仅一行一个数,表示满足条件的子串数。
Sample Input
aaaaa
1
Sample Output
6
HINT
对于 100%的数据:n<=15000 , k<=100,且字符集为所有小写字母。
Solution
这道题时限15s,明显O(n2)可以过。那么如果枚举某一端形成新的子串,用kmp的思想去处理的话,就可以过了。
那具体要如何处理这个子串呢?假设我们枚举左端点l,s长度为r,则形成的新子串为s[l...r]。
由题意我们可以知道,如果s[l...i]=s[j-i+l...j]且(i-l+1)>=k且l-1+(i-l+1)×2+1<=j,那么s[l...j]就是一个满足条件的子串,那么这道题就明显和Noi2014动物园很像了。
如果直接暴力用next[]找满足条件的前缀,实现会变成O(n3)。
所以这个地方得继续用kmp的思想:当发现现在的i不满足条件时,可以用next[]向前寻找满足条件的i。
这样的话,每次都是从满足(j-1)的条件的i开始寻找,于是时间复杂度就压到了O(n2)。
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 15002
using namespace std;
int next[N],n,k,ans;
char a[N];
inline void get_next(char a[]){
for(int i=,j=;a[i];i++){
while(j&&a[i]!=a[j+]) j=next[j];
j+=(a[i]==a[j+]);
next[i]=j;
}
for(int i=,j=;a[i];i++){
while(j&&a[i]!=a[j+]) j=next[j];
j+=(a[i]==a[j+]);
while(j&&j*>=i) j=next[j];
if(j>=k) ans++;
}
}
inline void init(){
scanf("%s%d",a+,&k);
n=strlen(a+);n-=(k<<);
for(int i=;i<n;i++)
get_next(a+i);
printf("%d",ans);
}
int main(){
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return ;
}
最新文章
- SSRS 实用技巧 ---- 为表格添加展开/折叠操作(明细报表)
- 一步一步配置NLB
- jquery mobile转场时加载js失效(转)
- 对象之间的引用传递 之 .NET中的深拷贝和浅拷贝
- Java线程同步_1
- 【动态规划】Vijos P1011 清帝之惑之顺治
- HDOJ 1715 大菲波数
- STMP发送邮件被当垃圾邮件处理的解决方法
- Fitnesse使用系列二
- Python 基金会 —— 模块和包简介
- POJ 1308 Is It A Tree? 解题报告
- Win10家庭版设置桌面右键更换桌面壁纸
- 手绘raft算法
- 安全圈玩起了直播,";学霸”带你玩转CTF
- cf1133 bcdef
- 第四百一十五节,python常用排序算法学习
- 使用Gitblit 搭建Windows Git服务器
- C#实现无标题栏窗体点击任务栏图标正常最小化或还原的解决方法
- 『Python』pycharm常用设置
- Mybatis中parameterType、resultMap、statementType等等配置详解(标签中基本配置详解)