比赛 20170519 评测结果 AAAAAAAAAA
题目名称 可疑的斑点 最终得分 100
用户昵称 31627012 运行时间 0.044 s
代码语言 C++ 内存使用 8.67 MiB
提交时间 2017-05-19 20:59:25
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
const double eps=1e-9;
inline void in(int &x){
    x=0;int f=1;char t=getchar();
    while(!isdigit(t)){if(t=='-')f=-1;t=getchar();}
    while(isdigit(t)){x=x*10+t-48;t=getchar();}
    x*=f;
}
int n,k,s;
int aa[100005][26],bb[100005][26];
int a[100005],b[100005];
bool cmp(int j,int i,int c1,int c2){
    int sum1=0,sum2=0;
    for(int k=1;k<c1;k++){
        sum1+=j?bb[j-1][k]:0;
    }
    for(int k=1;k<c2;k++){
        sum2+=(i?aa[i-1][k]:0)-((i-j)?aa[i-j-1][k]:0);
    }
    return sum1==sum2&&(j?bb[j-1][c1]:0)==((i?aa[i-1][c2]:0)-((i-j)?aa[i-j-1][c2]:0));
}
bool cmpp(int j,int i,int c1,int c2){
    int sum1=0,sum2=0;
    for(int k=1;k<c1;k++){
        sum1+=j?bb[j-1][k]:0;
    }
    for(int k=1;k<c2;k++){
        sum2+=(i?bb[i-1][k]:0)-((i-j)?bb[i-j-1][k]:0);
    }
    return sum1==sum2&&(j?bb[j-1][c1]:0)==((i?bb[i-1][c2]:0)-((i-j)?bb[i-j-1][c2]:0));
}
int nxt[100005];
inline void mk_pre(){
    for(int i=0;i<n;i++) {
        if(i)for(int j=1;j<=s;j++) aa[i][j]=aa[i-1][j];
        aa[i][a[i]]++;
    }
    for(int i=0;i<k;i++) {
        if(i)for(int j=1;j<=s;j++) bb[i][j]=bb[i-1][j];
        bb[i][b[i]]++;
    }
}
inline void mk(){
    int j=-1;
    nxt[0]=-1;
    for(int i=1;i<k;i++){
        while(~j&&!cmpp(j+1,i,b[j+1],b[i])) j=nxt[j];
        if(cmpp(j+1,i,b[j+1],b[i])) j++;
        nxt[i]=j;
    }
}
int ans[100005],top;
inline void work(){
    in(n);in(k);in(s);
    for(int i=0;i<n;i++){
        in(a[i]);
    }
    for(int i=0;i<k;i++){
    	in(b[i]);
    }
    mk_pre();
    mk();
    int j=-1;
    for(int i=0;i<n;i++){
        while(~j&&!cmp(j+1,i,b[j+1],a[i])) j=nxt[j];
        if(cmp(j+1,i,b[j+1],a[i])) j++;
        if(j==k-1){
            ans[top++]=i-j+1;
            j=nxt[j];
        }
    }
    printf("%d\n",top);
    for(int i=0;i<top;i++){
        printf("%d\n",ans[i]);
    }
}
inline int mian(){
    freopen("cpattern.in","r",stdin);
    freopen("cpattern.out","w",stdout);
    work();
}
int miku=mian();
int main(){;}