Jzoj3172 贴瓷砖

贴瓷砖"/>

Jzoj3172 贴瓷砖

A镇的主街是由N个小写字母构成，镇长准备在上面贴瓷砖，瓷砖一共有M种，第i种上面有Li个小写字母，瓷砖不能旋转也不能被分割开来，瓷砖只能贴在跟它身上的字母完全一样的地方，允许瓷砖重叠，并且同一种瓷砖的数量是无穷的。

问街道有多少字母(地方)不能被瓷砖覆盖。、

今天翻看题库发现这道题忘记写题解了。。。

非常好的卡常题，题目也很裸，直接AC自动机+前缀和判定就好了，但是当时不知道为什么用了fenwick

#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 300010
#define M 4000100
using namespace std;
int n,m,ans=0; char s[300010],t[5010];
struct fenwick{int w[N],S;inline void add(int x,int v){ for(;x<=m;x+=x&-x) w[x]+=v; }inline int sum(int x){ for(S=0;x;x&=x-1) S+=w[x]; return S; }
}w;
int fail[M],son[M][26],c[M],cnt=1,v[26];
inline void insert(char* s){int x=1,l=0;for(;*s;++s,++l){v[*s-'a']=1;x=son[x][*s-'a']?son[x][*s-'a']:son[x][*s-'a']=++cnt;}c[x]=l;
}
inline void build(){queue<int> q;for(int i=0;i<26;++i)if(!son[1][i]) son[1][i]=1;else q.push(son[1][i]),fail[son[1][i]]=1;for(int x;!q.empty();q.pop()){x=q.front();for(int i=0;i<26;++i)if(!son[x][i]) son[x][i]=son[fail[x]][i];else q.push(son[x][i]),fail[son[x][i]]=son[fail[x]][i];}	
}
inline void query(char* s){for(int i=1,x=1;*s;++s,++i){x=son[x][*s-'a'];for(int j=x;j!=1;j=fail[j])if(c[j]){ w.add(i-c[j]+1,1); w.add(i+1,-1); }}
}
int main(){scanf("%d%s",&m,s);scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%s",t); insert(t);}for(int i=0;i<m;++i) v[s[i]-'a']=0;for(int i=0;i<26;++i) if(v[i]) goto end;build(); query(s); end:for(int i=1;i<=m;++i) if(w.sum(i)==0) ++ans;printf("%d\n",ans);
}

转载于:.html