比赛 |
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(){;}