https://blog.csdn.net/a302549450/article/details/80948741?tdsourcetag=s_pctim_aiomsg
上面是题解的链接。。，
其实和kmp算法差不多，但是匹配的过程多了一些情况，还是挺有思维性的
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<map> #include<vector> #include<queue> using namespace std; #define PI acos(-1) #define INF 0x3f3f3f3f #define NUM 101000 #define debug false #define ll long long #define lowbit(x) ((-(x))&(x)) #define ffor(i,d,u) for(int i=(d);i<=(u);++i) #define _ffor(i,u,d) for(int i=(u);i>=(d);--i) #define mst(array,Num) memset(array,Num,sizeof(array)) const int p = 1e9+7; int n,k,m,_next[NUM],a[NUM<<1],b[NUM],ori[NUM<<1],par[NUM],pos[12]; int ans=0; template <typename T> void read(T& x) { x=0; char c; while((c=getchar())<'0'||c>'9'); do((x*=10)+=((int)(c-'0')));while((c=getchar())>='0'&&c<='9'); } template <typename T> void write(T x) { int len=0;char c[21]; if(x<0)putchar('-'); x=abs(x); do{++len;c[len]=(char)((x%10)+'0');}while(x/=10); _ffor(i,len,1)putchar(c[i]); } void build() { mst(pos,-1); par[1]=-1; pos[b[1]]=1; ffor(i,2,m) { if(pos[b[i]]!=-1) par[i]=i-pos[b[i]]; else par[i]=-1; pos[b[i]]=i; } mst(pos,-1); ori[1]=-1; pos[a[1]]=1; ffor(i,2,n) { if(pos[a[i]]!=-1&&i-pos[a[i]]<m) ori[i]=i-pos[a[i]]; else ori[i]=-1; pos[a[i]]=i; } } int getnext(int x) { int i; i=_next[x]; while(i!=-1 && par[i+1]!=par[x+1] && par[i+1]!=-1 )i=_next[i]; return i+1; } bool pd(int x,int y) { //母串的x和模式串的y相等 或者 模式串的y无前驱且(y前的长度比x前驱小) return (ori[x]==par[y] || (par[y]==-1 && ((y-ori[x])<1))); } void kmp() { _next[0]=-1;_next[1]=0; ffor(i,2,m) _next[i]=getnext(i-1); int i=0,j=0; while(j<n) { while(i<m&&j<n&&pd(j+1,i+1)){++i;++j;} if(i==m)++ans; if(j==n)break; while(i==m||(i!=-1&&!pd(j+1,i+1)))i=_next[i]; if(i==-1) { ++i; ++j; } } } void AC() { read(n),read(k); ffor(i,1,n) read(a[i]); read(m); ffor(i,1,m) read(b[i]); build(); kmp(); write(ans); } int main() { AC(); return 0; }