大致题意:
求文本串中最多能选出多少子串,使得这些子串和模式串匹配。这里匹配的标准是,串中任意两个位置大小关系相同。
大致思路:
对每个位置i求出 0---i中多少个值大于小于等于str[i]并根据这些值去匹配
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int nMax=100002; int n,m,k; int ttt[nMax],ppp[nMax],sum1[nMax][30],low1[nMax],high1[nMax],sum2[nMax][30],low2[nMax],high2[nMax]; int lent,lenp,next[nMax]; int equal1(int pa,int tb){ int i; if(tb==pa){ if(high1[tb]==high2[pa]&&low1[tb]==low2[pa]&&sum1[tb][ttt[tb]]==sum2[pa][ppp[pa]])return 1; else return 0; }else{ int low=0,high=0,sum=sum1[tb][ttt[tb]]-sum1[tb-pa-1][ttt[tb]]; for(i=1;i<=k;i++){ if(i<ttt[tb]){ low+=sum1[tb-pa-1][i]; }else if(i>ttt[tb]){ high+=sum1[tb-pa-1][i]; } } if(low1[tb]-low==low2[pa]&&high1[tb]-high==high2[pa]&&sum==sum2[pa][ppp[pa]])return 1; else return 0; } } void get_next(){ int i,j=-1; next[0]=-1; for(i=1;i<=lenp;i++){ //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符 while(j>-1&&ppp[j+1]!=ppp[i])j=next[j]; if(ppp[j+1]==ppp[i])j++; next[i]=j; } } int KMP(){ int ans=0,i=0,j=-1,last=-lenp-1; get_next(); for(i=0;i<lent;i++){ while(j!=-1&&!equal1(j+1,i)){//ppp[j+1]!=ttt[i] // cout<<j+1<<" edual1 "<<i<<endl; j=next[j]; } if(equal1(j+1,i)){ // cout<<j+1<<" edual1 "<<i<<endl; j=j+1; } if(j==lenp-1){ if(i-last>=lenp){ ans++; //找到一个匹配/ last=i; } } } return ans; } void init(){ lenp=m,lent=n; int i,j; memset(low1,0,sizeof(low1)); memset(low2,0,sizeof(low1)); memset(high1,0,sizeof(high1)); memset(high2,0,sizeof(high2)); memset(sum1,0,sizeof(sum1)); sum1[0][ttt[0]]=1; for(i=1;i<n;i++){ for(j=1;j<=k;j++){ sum1[i][j]=sum1[i-1][j]; if(j<ttt[i]){ low1[i]+=sum1[i][j]; }else if(j>ttt[i]){ high1[i]+=sum1[i][j]; } } sum1[i][ttt[i]]++; } memset(sum2,0,sizeof(sum2)); sum2[0][ppp[0]]=1; for(i=1;i<m;i++){ for(j=1;j<=k;j++){ sum2[i][j]=sum2[i-1][j]; if(j<ppp[i]){ low2[i]+=sum2[i][j]; }else if(j>ppp[i]){ high2[i]+=sum2[i][j]; } } sum2[i][ppp[i]]++; } } int main(){ int i,j; while(scanf("%d%d%d",&n,&m,&k)!=EOF){ for(i=0;i<n;i++)scanf("%d",&ttt[i]); for(i=0;i<m;i++)scanf("%d",&ppp[i]); init(); printf("%d\n",KMP()); } return 0; }
相关推荐
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
kmp算法 KMP算法是一种用于在一个文本串S中查找一个模式串P出现位置的高效算法。KMP算法的核心思想是利用模式串P本身的信息来避免在文本串S中进行不必要的匹配。具体来说,KMP算法通过预处理模式串P,构建一个部分...
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法
kmp算法用C语言编写+最短路径ShortestPath_DIJ编码
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法+全网最最最详细的代码注释,逐行注释,一看就懂,Code::Bclocks亲测完美运行!
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
kmp算法 kmp算法_基于Python+kmp算法实现模糊文本字符串匹配
kmp(kangle+mysql+php)集成版,支持asp、asp.net、php脚本环境,集成mysql数据库和phpmyadmin管理工具。kmp包含组件:kangle 2.1.8mysql-5.5.8php-5.2.17ZendOptimizer-3.3.9phpmyadmin-3.3.9
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
数据结构中KMP算法过程的Flash演示
基于KMP算法的字符串匹配源码, 支持通配符,单匹配和多重匹配。 效率比较高
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
串的替换,删除,查找 以及KMP算法的具体的实现 c语言 数据结构
...关于string的小结 kmp extend_kmp ac+trie 后缀数组
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。