AC自动机

  1. 1 【hdu 2222】Keywords Search
  2. 2 【hdu 2896】病毒侵袭
  3. 3 【hdu 3065】病毒侵袭持续中
  4. 4 【poj 2778】DNA Sequence
  5. 5 【hdu 2243】考研路茫茫——单词情结

trie+kmp=AC自动机

1 【hdu 2222】Keywords Search

找模式串有多少在总串中出现过

这不是个模板题吗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=50*10000+5;
int T,n,tot,tag[N],fail[N],trie[N][26];
char s[1000000];
void Add()
{
int len=strlen(s),pre=0;
for(int i=0;i<len;i++)
{
if(trie[pre][s[i]-'a']==-1)
{
trie[pre][s[i]-'a']=++tot;
for(int j=0;j<26;j++) trie[tot][j]=-1;
tag[tot]=0;
}
pre=trie[pre][s[i]-'a'];
}
tag[pre]++;
}
void Construct()
{
queue<int> Q;
fail[0]=0;
for(int i=0;i<26;i++)
{
if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
else trie[0][i]=0;
}
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=0;i<26;i++)
{
if(trie[x][i]!=-1)
{
Q.push(trie[x][i]);
fail[trie[x][i]]=trie[fail[x]][i];
}
else trie[x][i]=trie[fail[x]][i];
}
}
}
int Solve()
{
int pre=0,sum=0,len=strlen(s);
for(int i=0;i<len;i++)
{
pre=trie[pre][s[i]-'a'];
for(int j=pre;j;j=fail[j])
sum+=tag[j],tag[j]=0;
}
return sum;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);tot=0;tag[0]=0;
for(int i=0;i<26;i++) trie[0][i]=-1;
while(n--)
scanf("%s",s),Add();
Construct();
scanf("%s",s);
printf("%d\n",Solve());
}
return 0;
}

2 【hdu 2896】病毒侵袭

找哪些网站有哪些病毒

注意solve函数,不要算重了
还有要开128,因为是所有字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=500*200+5;
int n,tot,sum,ans[501],tag[N],fail[N],trie[N][128];
char s[10000];
bool used[501];
void Add(int t)
{
int len=strlen(s),pre=0;
for(int i=0;i<len;i++)
{
if(trie[pre][s[i]]==-1)
{
trie[pre][s[i]]=++tot;
for(int j=0;j<128;j++) trie[tot][j]=-1;
tag[tot]=0;
}
pre=trie[pre][s[i]];
}
tag[pre]=t;
}
void AC()
{
queue<int> Q;
fail[0]=0;
for(int i=0;i<128;i++)
{
if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
else trie[0][i]=0;
}
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=0;i<128;i++)
{
if(trie[x][i]!=-1)
{
Q.push(trie[x][i]);
fail[trie[x][i]]=trie[fail[x]][i];
}
else trie[x][i]=trie[fail[x]][i];
}
}
}
void Solve(int t)
{
int pre=0,len=strlen(s);
ans[0]=0;memset(used,0,sizeof(used));
for(int i=0;i<len;i++)
{
pre=trie[pre][s[i]];
for(int j=pre;j;j=fail[j])
if(tag[j]&&!used[tag[j]])
ans[++ans[0]]=tag[j],used[tag[j]]=1;
}
if(ans[0])
{
sum++;
sort(ans+1,ans+ans[0]+1);
printf("web %d:",t);
for(int i=1;i<=ans[0];i++) printf(" %d",ans[i]);
printf("\n");
}
}
int main()
{
scanf("%d",&n);
tag[0]=0;
for(int i=0;i<128;i++) trie[0][i]=-1;
for(int i=1;i<=n;i++)
scanf("%s",s),Add(i);
AC();
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",s),Solve(i);
printf("total: %d\n",sum);
return 0;
}

3 【hdu 3065】病毒侵袭持续中

找病毒出现的次数

多组数据也不说一声。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=50005;
int T,n,tot,ans[1001],tag[N],fail[N],trie[N][128];
char s[2000000],a[1001][50];
void Add(int t)
{
int len=strlen(a[t]),pre=0;
for(int i=0;i<len;i++)
{
if(trie[pre][a[t][i]]==-1)
{
trie[pre][a[t][i]]=++tot;
for(int j=0;j<128;j++) trie[tot][j]=-1;
tag[tot]=0;
}
pre=trie[pre][a[t][i]];
}
tag[pre]=t;
}
void AC()
{
queue<int> Q;
fail[0]=0;
for(int i=0;i<128;i++)
{
if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
else trie[0][i]=0;
}
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=0;i<128;i++)
{
if(trie[x][i]!=-1)
{
Q.push(trie[x][i]);
fail[trie[x][i]]=trie[fail[x]][i];
}
else trie[x][i]=trie[fail[x]][i];
}
}
}
void Solve()
{
int pre=0,len=strlen(s);
memset(ans,0,sizeof(ans));
for(int i=0;i<len;i++)
{
pre=trie[pre][s[i]];
for(int j=pre;j;j=fail[j])
if(tag[j]) ans[tag[j]]++;
}
}
int main()
{
while(scanf("%d",&n)==1)
{
tot=0;tag[0]=0;
for(int i=0;i<128;i++) trie[0][i]=-1;
for(int i=1;i<=n;i++)
scanf("%s",a[i]),Add(i);
AC();
scanf("%s",s);
Solve();
for(int i=1;i<=n;i++)
if(ans[i]) printf("%s: %d\n",a[i],ans[i]);
}
return 0;
}

4 【poj 2778】DNA Sequence

有ATCG的DNA,有m种排列为患病,求长度为n中正常的数量

看到题目的第一眼,我开始读:D(dǐ)NA序列。。。。。。陈林大法好。。。
算了不扯了。。。
AC自动机+矩阵乘法
先是RE了,因为我把tot写成了n
然后TLE了,解决方法是矩阵开long long,然后把mod写到外面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=105;
const int mod=100000;
int m,n,tot,id[26],fail[N],trie[N][4];
long long ans,g[N][N],res[N][N],c[N][N];
char s[10];
bool tag[N];
void Add()
{
int len=strlen(s),pre=0;
for(int i=0,ID;i<len;i++)
{
ID=id[s[i]-'A'];
if(trie[pre][ID]==-1)
{
trie[pre][ID]=++tot;
for(int j=0;j<26;j++) trie[tot][j]=-1;
tag[tot]=0;
}
pre=trie[pre][ID];
}
tag[pre]=1;
}
void Construct()
{
queue<int> Q;
fail[0]=0;
for(int i=0;i<4;i++)
{
if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
else trie[0][i]=0;
}
while(!Q.empty())
{
int x=Q.front();Q.pop();
if(tag[fail[x]]) tag[x]=1;
for(int i=0;i<4;i++)
{
if(trie[x][i]!=-1)
{
Q.push(trie[x][i]);
fail[trie[x][i]]=trie[fail[x]][i];
}
else trie[x][i]=trie[fail[x]][i];
}
}
for(int i=0;i<=tot;i++)
for(int j=0;j<4;j++)
if(!tag[i]&&!tag[trie[i][j]]) g[i][trie[i][j]]++;
}
void Multi(long long a[N][N],long long b[N][N],int flag)
{
memset(c,0,sizeof(c));
for(int i=0;i<=tot;i++)
for(int j=0;j<=tot;j++)
{
for(int k=0;k<=tot;k++)
c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=mod;
}
if(!flag) memcpy(g,c,sizeof(g));
else memcpy(res,c,sizeof(c));
}
void power(int b)
{
for(int i=0;i<N;i++) res[i][i]=1;
for(;b;b>>=1,Multi(g,g,0))
if(b&1) Multi(res,g,1);
}
int main()
{
scanf("%d%d",&m,&n);
id['A'-'A']=0;id['T'-'A']=1;id['C'-'A']=2;id['G'-'A']=3;
tot=0;tag[0]=0;
for(int i=0;i<4;i++) trie[0][i]=-1;
while(m--)
scanf("%s",s),Add();
Construct();
power(n);
for(int i=0;i<=tot;i++)
ans+=res[0][i];
printf("%d\n",ans%mod);
}

5 【hdu 2243】考研路茫茫——单词情结

有N个词根,问长度不超过L的单词中包含词根的数量

mod2642^{64} 相当于开unsigned long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=35;
int L,n,tot,id[26],fail[N],tag[N],trie[N][26];
unsigned long long ans1,ans2,g[N][N],res[N][N],c[N][N];
queue<int> Q;
char s[6];
void Add()
{
int len=strlen(s),pre=0;
for(int i=0;i<len;i++)
{
if(trie[pre][s[i]-'a']==-1)
{
trie[pre][s[i]-'a']=++tot;
memset(trie[tot],-1,sizeof(trie[tot]));
tag[tot]=0;
}
pre=trie[pre][s[i]-'a'];
}
tag[pre]=1;
}
void Construct()
{
fail[0]=0;
for(int i=0;i<26;i++)
{
if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
else trie[0][i]=0;
}
while(!Q.empty())
{
int x=Q.front();Q.pop();
if(tag[fail[x]]) tag[x]=1;
for(int i=0;i<26;i++)
{
if(trie[x][i]!=-1)
{
Q.push(trie[x][i]);
fail[trie[x][i]]=trie[fail[x]][i];
}
else trie[x][i]=trie[fail[x]][i];
}
}
memset(g,0,sizeof(g));
for(int i=0;i<=tot;i++)
for(int j=0;j<26;j++)
if(!tag[i]&&!tag[trie[i][j]]) g[i][trie[i][j]]++;
for(int i=0;i<=tot+1;i++)
g[i][tot+1]=1;
}
void Multi(unsigned long long a[N][N],unsigned long long b[N][N],int flag,int t)
{
memset(c,0,sizeof(c));
for(int i=0;i<=t;i++)
for(int j=0;j<=t;j++)
for(int k=0;k<=t;k++)
c[i][j]+=a[i][k]*b[k][j];
if(!flag) memcpy(g,c,sizeof(c));
else memcpy(res,c,sizeof(c));
}
void power(int b,int t)
{
memset(res,0,sizeof(res));
for(int i=0;i<N;i++) res[i][i]=1;
for(;b;b>>=1,Multi(g,g,0,t))
if(b&1) Multi(res,g,1,t);
}
int main()
{
while(scanf("%d%d",&n,&L)==2)
{
tot=0;tag[0]=0;
memset(trie[0],-1,sizeof(trie[0]));
for(int i=1;i<=n;i++)
scanf("%s",s),Add();
Construct();
power(L,tot+1);
ans1=0;
for(int i=0;i<=tot+1;i++)
ans1+=res[0][i];
g[0][0]=26;g[0][1]=0;g[1][0]=g[1][1]=1;
power(L,1);
ans2=res[1][0]+res[0][0];
printf("%llu\n",ans2-ans1);
}
}