BZOJ 1461: 字符串的匹配

Description

同上题.

Sol

KMP+树状数组.

写这题的时候我灰常naive...不管了...直接贴代码...

Code

/**************************************************************
Problem: 1461
User: BeiYu
Language: C++
Result: Accepted
Time:756 ms
Memory:13032 kb
****************************************************************/ #include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 500005
#define M 10005
int a[N],b[N],rk1[N],rk2[N],f[N],ans[N];int c[M];
int n,m,s,t;
inline int in(int x=0,char ch=getchar()){
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int v){while(x<=s) c[x]+=v,x+=lowbit(x);}
inline int sum(int x,int res=0){while(x) res+=c[x],x-=lowbit(x);return res;}
int main(){
n=in(),m=in(),s=in();
for(int i=0;i<n;i++) a[i]=in();
for(int i=0;i<m;i++) b[i]=in(),add(b[i],1),rk1[i]=sum(b[i]-1),rk2[i]=sum(b[i]);
memset(c,0,sizeof(c));
for(int i=1,j;i<m;i++){
j=f[i];add(b[i],1);
while(j&&(sum(b[j]-1)!=rk1[i]||sum(b[j])!=rk2[i])){
for(int p=i-j;p<i-f[j];p++) add(b[p],-1);
j=f[j];
}
f[i+1]=(rk1[j]==sum(b[i]-1)&&rk2[j]==sum(b[i]))?j+1:0;
}
memset(c,0,sizeof(c));
for(int i=0,j=0;i<n;i++){
add(a[i],1);
while(j&&(sum(a[i]-1)!=rk1[j]||sum(a[i])!=rk2[j])){
for(int p=i-j;p<i-f[j];p++) add(a[p],-1);
j=f[j];
}
if(sum(a[i]-1)==rk1[j]&&sum(a[i])==rk2[j]) j++;
if(j==m){
ans[++t]=i-j+1;
for(int p=i-j+1;p<=i;p++) add(a[p],-1);
j=0;
}
}
printf("%d\n",t);
for(int i=1;i<=t;i++) printf("%d\n",ans[i]+1);
return 0;
}

  

上一篇:hadoop分布式安装教程(转)


下一篇:数据库启动与关闭