zoj 3228 覆盖及非覆盖串的多次匹配

题目题意:

给定多个小串,在一个长串中寻找这些串的匹配次数,有些统计的是可覆盖的,有些统计的是非覆盖的

先可以简单理解一下,建立ac自动机后,当前节点包含的字符串必然被把它作为fail指针的节点包含,所以一开始写了个set[MAX],然后MLE了

如果一个当前串被完全访问了,那么这个串一定是在整个fail指针的最后面的,所以那个节点在访问中一直沿着fail指针往下走一定是能走到的,在记录一个

上一次访问的位置,就能判断当前位置是否重复覆盖了

然后根据初始记录的字符串对应的节点位置,输出在那个节点的访问次数就行了

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
using namespace std;
#define clr(x) memset(x , 0 , sizeof(x))
#define CHAR_SIZE 26
#define MAX_SIZE 600010
#define N 100005
char str[MAX_SIZE];
char s[];
int n , cnt[MAX_SIZE][];
int pos[N] , flag[N];
struct AC_Machine{
int sz , ch[MAX_SIZE][CHAR_SIZE] , fail[MAX_SIZE] , deep[MAX_SIZE] , val[MAX_SIZE] , pre[MAX_SIZE];
void init(){
sz = ;
clr(ch[]) , clr(val);
pre[] = ;
cnt[][] = cnt[][] = ;
} void insert(char *s , int p){
int n = strlen(s) , u=;
for(int i= ; i<n ; i++){
int c = s[i]-'a';
if(!ch[u][c]){
clr(ch[sz]);
cnt[sz][] = cnt[sz][] = pre[sz] = val[sz] = ;
ch[u][c] = sz++;
}
u = ch[u][c];
deep[u] = i+;
}
val[u] = ;
pos[p] = u;
} void get_fail(){
queue<int> Q;
fail[] = ;
for(int c= ; c<CHAR_SIZE ; c++){
int u = ch[][c];
if(u) {Q.push(u);fail[u]=;}
}
while(!Q.empty()){
int r = Q.front();
val[r] |= val[fail[r]];
Q.pop();
for(int c= ; c<CHAR_SIZE ; c++){
int u = ch[r][c];
if(!u){ch[r][c]=ch[fail[r]][c] ; continue;}
fail[u] = ch[fail[r]][c];
Q.push(u);
}
}
}
}ac; void solve()
{
int cur = , n=strlen(str);
for(int i= ; i<=n ; i++){
int c = str[i-]-'a';
cur = ac.ch[cur][c];
int v = cur;
while(v && ac.val[v]){
cnt[v][]++;
// cout<<str[i-1]<<" "<<v<<endl;
if(i-ac.pre[v]>=ac.deep[v]){
cnt[v][]++;
ac.pre[v] = i;
}
v = ac.fail[v];
}
}
} int main()
{
// freopen("in.txt" , "r" , stdin);
int cas = ;
while(~scanf("%s" , str))
{
printf("Case %d\n" , ++cas);
scanf("%d" , &n);
int op;
ac.init();
for(int i= ; i<=n ; i++){
scanf("%d%s" , &op , s);
flag[i] = op;
ac.insert(s , i);
}
ac.get_fail();
solve(); for(int i= ; i<=n ; i++){
printf("%d\n" , cnt[pos[i]][flag[i]]);
}
puts("");
}
return ;
}
上一篇:方案:手动升级WordPress系统


下一篇:Note: SE Class's Individual Project