大致题意:
给出一个模式串P和一个文本串T求存在多少种数字组合(a,b,c,d)使得Ta..b + Tc..d = P。
大致思路:
可以用KMP求出模式串的每个前缀在文本串中出现的次数,再把字符串翻转过来,求出模式串的每个后缀在文本串中出现的次数,最后统计一下即可~~
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=10005;
const int mMax=1000005;
char text[mMax],pat[nMax];
int lent,lenp,next[nMax];
long long a[nMax],b[nMax];
void get_next(){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenp;i++){ //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符
while(j>-1&&pat[j+1]!=pat[i])j=next[j];
if(pat[j+1]==pat[i])j++;
next[i]=j;
}
}
int KMP(int flag){
int ans=0,i=0,j=-1;
get_next();
for(i=0;i<lent;i++){
while(j!=-1&&pat[j+1]!=text[i]){
j=next[j];
}
if(pat[j+1]==text[i])j=j+1;
if(j==lenp-1)ans++; //找到一个匹配
if(j!=-1){
if(flag)a[j]++;
else b[j]++;
}
}
return ans;
}
int main(){
int t,i,tmp;
long long ans;
scanf("%d",&t);
while(t--){
ans=0;
scanf("%s%s",text,pat);
lenp=strlen(pat);
lent=strlen(text);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
KMP(1);
for(i=lenp;i!=-1;i--){
if(next[i]!=-1) a[next[i]]+=a[i];
}
for(i=0;i<lent/2;i++){
tmp=text[i];
text[i]=text[lent-i-1];
text[lent-i-1]=tmp;
}
for(i=0;i<lenp/2;i++){
tmp=pat[i];
pat[i]=pat[lenp-i-1];
pat[lenp-i-1]=tmp;
}
// cout<<pat<<" "<<text<<endl;
KMP(0);
for(i=lenp;i!=-1;i--){
if(next[i]!=-1) b[next[i]]+=b[i];
}
// for(i=0;i<lenp;i++){
// cout<<"a"<<a[i]<<" b"<<b[i]<<endl;
// }
for(i=0;i<lenp-1;i++){
ans+=a[i]*b[lenp-i-2];
}
cout<<ans<<endl;
// for(i=0;i<lenp;i++){
// cout<<"a"<<a[i]<<endl;
// }
}
return 0;
}
分享到:
相关推荐
KMP算法,详细的解释了如何去匹配字符串。做成了实验报告,希望给大家帮助。
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
D-KMP体系结构-官方样本这是D-KMP架构的官方示例,展示了一个适用于Android和iOS的简单主/详细应用程序。 有关D-KMP体系结构的更多信息,请阅读相关的。D-KMP体系结构的主要功能: 它使用最新的声明性UI工具包:适用...
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
KMP算法 字符串匹配算法 The KMP algorithm string matching algorithm
int index(const std::string &s, const std::string &p, const int sIndex = 0) { int i = sIndex, j = 0; if (s.length() || p.length() || sIndex ) { return -1; } while (i != s.length() && j != p....
void kmp_matcher(sstring s,sstring s1) { int i = 1,j=1; /* Number of characters mached */ int n = s.length; int m = s1.length; int *x = get_next (s1); while(i) { if(j==0 || s.p[i]==s1.p[j])...
kmp 字符串匹配 算法 C语言实现 函数
KMP报告:元宇宙产品概念,哪一种消费者更有感 12.15-31页.pdf
KMP扩展器 适用于CSV文件的Mario Kart 7的KMP编辑器。
kmp算法
D-KMP架构Daniele Baroncelli建议的D-KMP体系结构的试用示例,位于: ://danielebaroncelli.medium.com/the-future-of-apps-declarative-uis-with-kotlin-multiplatform-d-kmp-part-1 它:声明性UI(Jetpack编写)...
模板-kmp-库 Kotlin多平台库模板。 有一个针对多平台库的基线设置,该库支持除弃用的wasm32之外的所有kotlin。 特征 本机目标分组和共享sourceSet 包装程序库模块,它声明对所有lib模块的依赖关系 通过allprojects...
一个封装有KMP模式匹配算法的String类示例,VC++ 2010下编译通过。
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
问题:串的模式匹配算法---KMP 方法:从主串S中寻找模式串T出现的位置。 基本思想:从主串S的第1个字符起和模式串T的第一个字符比较,若相等,则继续逐个比较后续字符;否则从主串的下一个字符再重新和模式的字符...
kmp算法:查找一个字符串是不是另一个字符串的子串
模式匹配,KMP算法,string-match-kmp-master.zip
利用KMP算法进行子串的快速查找,能够达到较高的速率
扩展的KMP问题: 给定母串S,和子串T。 定义n=|S|, m=|T|,extend[i]=S[i..n]与T的最长公共前缀长度。请在线性的时间复杂度内,求出所有的extend[1..n]。