给定一个主串S(长度为n)以及t个模式串P(长度为m),问有多少个模式串,可以由主串中的左右两个模式串拼成。
首先枚举划分母串的位置i,左边是S[1~i],右边是S[i+1,n]。那么,假设“左边”和“子串P的前缀”的最长匹配长度为len1,“右边”和“子串P的后缀”的最长匹配长度为len2,如果len1+len2>=m,说明能够拼成模式串。
kmp算法中f[i]表示“母串S以i结尾的后缀”和“子串P的前缀”的能够匹配的最长长度,那么len1就等于f[1~i]中的最大值。同理,翻转主串和模式串再跑一次kmp就可以求出len2。
1、当模式串长度为1时,直接跳过,因为不能由两个串拼成。
2、 不要一直调用strlen,定义全局变量或传参,T了好几发,落泪。
3、 做完一个模式串之后再把主串翻转回来。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char a[N],b[N];
int f[2][N],nxt[2][N];
int n,ans,la,lb;
void getnxt(char *p,int k){
nxt[k][1]=0;
for(int i=2,j=0;i<=lb;i++){
while(j>0&&p[i]!=p[j+1]) j=nxt[k][j];
if(p[i]==p[j+1]) j++;
nxt[k][i]=j;
}
}
void kmp(char *s,char *p,int k){
for(int i=1,j=0;i<=la;i++){
while(j>0&&(j==lb||s[i]!=p[j+1])) j=nxt[k][j];
if(s[i]==p[j+1]) j++;
f[k][i]=j;
}
}
int main(){
scanf("%s",a+1);
scanf("%d",&n);
la=strlen(a+1);
for(int i=1;i<=n;i++){
scanf("%s",b+1);
lb=strlen(b+1);
if(lb==1) continue;
getnxt(b,0);
kmp(a,b,0);
reverse(a+1,a+la+1);
reverse(b+1,b+lb+1);
getnxt(b,1);
kmp(a,b,1);
for(int i=1;i<=la;i++){
f[0][i]=max(f[0][i-1],f[0][i]);
f[1][i]=max(f[1][i-1],f[1][i]);
}
bool flag=0;
for(int i=1;i<la;i++){
int j=la-i;
if(!f[0][i]||!f[1][j]) continue;
if(f[0][i]+f[1][j]>=lb){
flag=1;
break;
}
}
if(flag) ans++;
reverse(a+1,a+la+1);
}
printf("%d\n",ans);
return 0;
}
原文:https://www.cnblogs.com/qjy73/p/12459283.html