HDU4749 Parade Show(KMP)
2024-10-10 09:58:39
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4749
题意:给出两个数字串A、B。问A中有多少不相交的子串a能匹配B。匹配的意思是a中任意两个位置i和j的大小关系和B的这两个位置的大小关系是一样的。
思路:若是完全一模一样的匹配的话那么KMP是很好理解的。那么对于上述的比较方式怎么比较两个串相等呢?对于a的位置i和B的位置i,我们只要比较i之前a中a[i]的个数和B中B[i]的个数是否相等,以及a中小于a[i]的个数和B中小于B[i]的数字个数是否相等。只要每个位置都满足则这两个串匹配。
int f[N][30],g[N][30],next[N]; int a[N],b[N],n,m,K; int visit[N]; int ok(int x,int y) { if(g[x][b[x]]!=g[y][b[y]]-g[y-x][b[y]]) return 0; int cnt1=0,cnt2=0,i; for(i=1;i<b[x];i++) cnt1+=g[x-1][i]; for(i=1;i<b[y];i++) cnt2+=g[y-1][i]; for(i=1;i<b[y];i++) cnt2-=g[y-x][i]; return cnt1==cnt2; } void getNext() { next[1]=0; int i,j=0; for(i=2;i<=m;i++) { while(j&&!ok(j+1,i)) j=next[j]; if(ok(j+1,i)) j++; next[i]=j; } } int ok1(int x,int y) { if(g[x][b[x]]!=f[y][a[y]]-f[y-x][a[y]]) return 0; int cnt1=0,cnt2=0,i; for(i=1;i<b[x];i++) cnt1+=g[x-1][i]; for(i=1;i<a[y];i++) cnt2+=f[y-1][i]; for(i=1;i<a[y];i++) cnt2-=f[y-x][i]; return cnt1==cnt2; } void kmp() { int i,j=0; for(i=1;i<=n;i++) { while(j&&!ok1(j+1,i)) j=next[j]; if(ok1(j+1,i)) j++; if(j==m) visit[i]=1,j=next[j]; } } int main() { while(cin>>n>>m>>K) { clr(f,0); clr(g,0); clr(visit,0); int i,j; FOR1(i,n) { RD(a[i]); FOR1(j,K) f[i][j]=f[i-1][j]; f[i][a[i]]++; } FOR1(i,m) { RD(b[i]); FOR1(j,K) g[i][j]=g[i-1][j]; g[i][b[i]]++; } getNext(); kmp(); int ans=0; i=1; while(i<=n) { if(visit[i]) i+=m,ans++; else i++; } PR(ans); } }
最新文章
- js-JavaScript高级程序设计学习笔记7
- pcA降维算法
- 洛谷 P1025 数的划分 Label:dp
- iOS开发经验总结(转)
- C# 学习之旅(2)--- 意外的收获
- ThreadPool
- 浅谈-Lambda
- 手机自动化测试:搭建appium手机自动化测试开发环境
- Java中的大小写字母相互转换(不利用Java自带的方法)
- Java【初识篇】语言概述
- 【Luogu4916】魔力环(Burnside引理,组合计数)
- zookeeper集群和安装dubbo的管控台
- CSS3 Flexbox可视化指南
- windows下安装和配置多个版本的JDK
- CCCC L2-013. 红色警报 连通分量
- C#中的三种timer
- Ubuntu Server 下的网络配置
- 【转】VC++10(VS2010)IDE各种使用技巧
- CASE语句用法学习
- Jquery把获取到的input值转换成json
热门文章
- hdu 2686 Matrix 最小费用最大流
- Leetcode#123 Best Time to Buy and Sell Stock III
- 2014ACM/ICPC亚洲区北京站 上交命题
- window.showModalDialog的传值和返回值
- Linux软件安装方法小结(附:rpm详解)(转载)
- SOA之(4)——服务实现的途径
- codeforces 459C Pashmak and Buses(模拟,组合数A)
- 传说中的WCF(3):多个协定
- Linux网络编程2&mdash;&mdash;系统函数
- node操作mysql数据库