本篇题解用于作者本人加深理解，也欢迎大家阅读。

---

这道题的正解是\(KMP\)加上树状数组，记录每一个位置前几个位置比其小的、相等的、大的数的数量，比较方式便是比较相应的数量，若相等，则匹配成功。

但是本篇题解使用了\(Hash\)的做法，因为\(1<=s<=25\)，所以我们可以利用一个数组，并利用二进制的压缩方式，记录每一个数存在的位置。即：

\(hash[i]\)表示数字\(i\)在\(k\)的长度中出现的位置的二进制压缩。

如\(hash[i]=1000101_2\)就表示\(i\)在长度为\(k=7\)的序列内出现在了\(1,5,7\)的位置（\(or\)出现在了\(1 ,3,7\)的位置（看个人理解）），接着再按照\(s\)从小到大比较二进制压缩，即可判断是否一致。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100005,M=25005,S=30,MOD=7710343;
int n,m,s,len;
int a[N],b[M];
ll ksm[M],hsa[S],hsb[S];
int ans[N],lans=0;
inline int read()
{
    char c=getchar();
    while(c<'0'||'9'<c)
    c=getchar();
    int x=0;
    while('0'<=c&&c<='9')
    {
        x*=10;
        x+=c-'0';
        c=getchar();
    }
    return x;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;++i)
    a[i]=read();
    for(int i=1;i<=m;++i)
    b[i]=read();
    ksm[0]=1;
    for(int i=1;i<=m;++i)
    ksm[i]=ksm[i-1]*2%MOD;
    for(int i=1;i<=m;++i)
    {
        len=max(len,b[i]);
        for(int j=1;j<=s;++j)
        {
            hsb[j]=(hsb[j]*2+(b[i]==j))%MOD;
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=s;++j)
        {
            hsa[j]=(hsa[j]*2+(a[i]==j))%MOD;
        }
        if(i>=m)
        {
//            printf("%d\n",i-m+1);
            bool ok=true;
            int aa=1,bb=1,cnt=0;
            while(aa<=s&&bb<=s)
            {
                while(aa<=s&&!hsa[aa])
                ++aa;
                while(bb<=s&&!hsb[bb])
                ++bb;
                if(aa>s||bb>s)
                break;
                if(hsa[aa]==hsb[bb])
                {
                    ++cnt;
//                    printf("%d %d\n",aa,bb);
                }
                else
                {
                    ok=false;
                    break;
                }
                ++aa;
                ++bb;
            }
//            printf("%d %d %d\n",cnt,len,ok);
            if(cnt==len&&ok)
            ans[++lans]=i-m+1;
            for(int j=1;j<=s;++j)
            {
                hsa[j]=((hsa[j]-ksm[m-1]*(a[i-m+1]==j))%MOD+MOD)%MOD;
            }
        }
    }
    printf("%d\n",lans);
    for(int i=1;i<=lans;++i)
    printf("%d\n",ans[i]);
    return 0;
}