rt

$O(n^2)$ 的暴力枚举加 $Sunday$ 匹配字符串可以跑过90分，带个特殊性质特判可A

#include<iostream>
#include<string.h>
#include<bitset>
#include<vector>
using namespace std;
const int MAXN=5000005;
int a,b,c,tot=0,cnt=0,res=0,Gcd,query,sum=0,maxx=0;
int cmp[MAXN],val[MAXN],num[MAXN],ask[MAXN];
int shift[15];
bitset<MAXN> bj;
int dx[MAXN],sjb[MAXN];
int s1[MAXN],s2[MAXN];
int que[MAXN*32],nxt[MAXN*32];
vector<int> lct;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
inline char bit()
{
    static char buf[105],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,105,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    #define getchar() bit()
    char x=getchar();int t=0;
    while(!isdigit(x))x=getchar();
    while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
    return t;
}
char buf[1024];
int p=0;
inline void pc(int x)
{
    buf[p++]=x;
    if(p==1024)fwrite(buf,1024,1,stdout),p=0;
}
inline void print(int x)
{
//    #define pc(x) putchar(x)
    short stk[10],to=0;
    while(x)stk[++to]=x%10,x/=10;
    while(to)pc(stk[to--]^48);
}
//int kmp(int x1[],int x2[],int len1,int len2)
//{
//    bj.reset();
//    vector<int> lct;
//
//    for(register int i=0;i<=10;++i)shift[i]=len2+1;
//    for(register int i=0;i<len2;++i)shift[x2[i]]=len2-i;
//    int head=0,j=0;
//    while(head<=len1-len2)
//    {
//        j=0;
//        while(x1[head+j]==x2[j])
//        {
//            j++;
//            if(j>=len2&&bj[head+1]==0)
//            {
//                bj[head+1]=1;
//                lct.push_back(head+1);
//            }
//        }
//        head+=shift[x1[head+len2]];
//    }
//    return lct.size();
//}
int sunday(int x1[],int x2[],int len1,int len2)
{
    int k=0,s=0;
    for(register int i=1;i<len2;++i)
    {
        while(k&&x2[i]!=x2[k])k=nxt[k];
        nxt[i+1]=x2[i]==x2[k]?++k:0;
    }
    for(register int i=0,j=0;i<len1;++i)
    {
        if(x1[i]==x2[j]&&j<len2)++j;
        else while(j>0)
        {
            j=nxt[j];
            if(x1[i]==x2[j]){j++;break;}
        }
        if(j==len2)s++;
        if(len2==cnt)lct.push_back(i-len2+2);
    }
    return s;
}
int main()
{
    a=read();b=read();

    for(register int i=0;i<a;++i)ask[i]=read();
    for(register int i=1;i<=b;++i)cmp[i]=read();
    for(register int i=1;i<=b;++i)
    {
        if(cmp[i]!=cmp[i-1])val[++tot]=cmp[i];
        maxx=max(maxx,s2[tot]=++num[tot]);
    }
    query=num[1];
    for(register int i=2;i<=tot;++i)query=gcd(query,num[tot]);
    for(register int i=1;i<=tot;++i)num[i]/=query;
    for(register int i=1;i<=tot;++i)
        for(register int j=1;j<=num[i];++j)
            dx[cnt++]=val[i];

    for(register int i=1;i<=maxx;++i)
    {
        tot=0;
        for(register int j=0;j<cnt;++j)
            for(register int k=1;k<=i;++k)
                que[tot++]=dx[j];
//        int query=kmp(ask,que,a,tot);
        int query=sunday(ask,que,a,tot);
        sum+=query;
        if(cnt==1)
        {
            sum=0;
            int to=0;
            int len=1;
            long long ans=0;
            for(int j=0;j<a;++j)
            {
                if(ask[j]==cmp[1])
                {
                    len=1;
                    while(ask[j+1]==cmp[1])
                        len++,j++;
                    for(int k=1;k<=len;++k)ans+=k;
                }
            }
            cout<<ans;
            return 0;
            break;
        }
        if(!query)break;
    }
    print(sum);
    fwrite(buf,p,1,stdout);
    fflush(stdout);
    return 0;
}