poj 3461 Oulipo(kmp统计子串出现次数)
2024-08-30 12:12:34
题意:统计子串出现在主串中的次数
思路:典型kmp
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; int next[]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;
k=-;
next[]=-;
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){
++j;
++k;
next[j]=k;//此句可由优化替代
/*优化(仅保证求KMPIndex时可用。谨慎使用。)
if(t[j]!=t[k])next[j]=k;
else next[j]=next[k];
*/
}
else k=next[k];
}
} int KMPIndex(char s[],char t[]){//求子串首次出现在主串中的位置
int i,j,lens,lent;
i=j=;
lens=strlen(s);
lent=strlen(t); while(i<lens&&j<lent){
if(j==-||s[i]==t[j]){
++i;
++j;
}
else j=next[j];
}
if(j>=lent)return i-lent;
else return -;
} int KMPCount(char s[],char t[]){//统计子串在主串中的出现次数,可重叠
int i,j,lens,lent,cnt;
i=j=;
lens=strlen(s);
lent=strlen(t);
cnt=; while(i<lens){
if(j==-||s[i]==t[j]){
++i;
++j;
}
else j=next[j];
if(j==lent)++cnt;
}
return cnt;
} void KMPCount2(char t[]){//统计单串中从某个位置以前有多少重复的串
int i,lent,tmp;
lent=strlen(t); for(i=;i<=lent;++i){
tmp=i-next[i];
if(i%tmp==&&i/tmp>)
printf("\t位置:%d 个数:%d\n",i,i/tmp);
}
} int main(){
char str1[],str2[];
int i;
int t;
scanf("%d",&t);
while(t--){
scanf("%s%s",str2,str1);
GetNext(str2);//求子串的next数组
printf("%d\n",KMPCount(str1,str2));
}
return ;
}
最新文章
- 豆芽儿 - 高端IT人才成长社区 上线啦!
- 解决httpd: Could not reliably determine the server&#39;s fully qualified domain name
- iOS开发的一些奇巧淫技
- ubuntu安装vmware tools
- try catch语句在VC下的处理
- 【转】JSON简介以及用法代码汇总
- 窗函数的C语言实现
- spring学习总结(mybatis,事务,测试JUnit4,日志log4j&;slf4j,定时任务quartz&;spring-task,jetty,Restful-jersey等)
- [NOIP 2011]聪明的质监员
- Java多线程synchronized关键字
- obj-c编程19:关联对象
- form中的button默认提交事件
- Discuz3.2与Java 项目整合单点登陆
- 如何在idea中引入一个新maven项目
- 2019.02.21 bzoj5317: [Jsoi2018]部落战争(凸包+Minkowski和)
- (转载)Ubuntu下安装Qt
- Daily Scrum 10.22
- Verilog三段式状态机描述
- Thrift-RPC client in Flume
- AC日记——魔法森林 洛谷 P2387
热门文章
- bootstrap-datatables
- 安卓解析JSON文件
- SpringCloud-Eureka注册中心
- Spring MVC使用Schedule实现定时任务
- Go -- 通过GOTRACEBACK生成程序崩溃后core文件的方法(gcore gdb)
- Building a Radio Listening Station to Decode Digital Audio &; Police Dispatches
- palindrome-partitioning I&;II——回文切割、深度遍历
- 一个TAB的jquery简单写法2
- 1 npoi 网上 不用模板 设置密码 workbook.WriteProtectWorkbook(";password";, ";admin";); 、、 2 locked.IsLocked = true; sheet1.ProtectSheet(";password";);NPOI操作EXCEL--设置密码才可以修改单元格内容 3 模板设置密码 确定原密码 设置新密码
- java基础知识汇总6(html篇)