通过此题加上POJ 3691我对自动机有了更深的了解，不仅仅局限于字符串匹配，原来它是一种转移状态的机器。。。Orz。
POJ 2778
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MOD=100000;
//******************************************Trie部分********************************************
struct Trie
{
Trie *fail;
Trie *next[4];
bool isdanger;
int num;
Trie()
{
memset(next,NULL,sizeof(next));
fail=NULL;
isdanger=0;
}
}*root,*T[10000];
int idx=0;
void NewTrie()
{
T[idx]=new Trie();
T[idx]->num=idx;
}
void Init()
{
idx=0;
NewTrie();
root=T[idx++];
}
int id(char s)
{
switch(s)
{
case 'A': return 0;
case 'T': return 1;
case 'G': return 2;
case 'C': return 3;
}
}
void Insert(char *s)
{
int j;
Trie *r=root;
for(j=0;j<strlen(s);j++)
{
int i=id(s[j]);
if(r->next[i]==NULL)
{
NewTrie();
r->next[i]=T[idx++];
}
r=r->next[i];
}
r->isdanger=1;
}
void BuildTrie()
{
Trie *r=root,*p;
queue<Trie *>q;
root->fail=root;
root->isdanger=0;
q.push(root);
while(!q.empty())
{
p=q.front();
q.pop();
p->isdanger=p->isdanger||p->fail->isdanger;
for(int i=0;i<4;i++)
{
if(p->next[i]==NULL)//如果p->next[i]为空，则赋值为p的后缀的next[i]
{
if(p==root)
p->next[i]=root;
else
p->next[i]=p->fail->next[i];
}
else //如果p->next[i]不为空，则构造后缀(失败)节点
{
if(p==root)
p->next[i]->fail=root;
else
p->next[i]->fail=p->fail->next[i];
q.push(p->next[i]);
}
}
}
}
//******************************************矩阵乘法部分**********************************
struct MT
{
__int64 mt[110][110];
};
MT Mult(MT a,MT b)
{
int i,j,k;
MT res;
memset(res.mt,0,sizeof(res.mt));
for(i=0;i<idx;i++)
for(j=0;j<idx;j++)
if(a.mt[i][j])//矩阵乘法优化
{
for(k=0;k<idx;k++)
{
res.mt[i][k]+=(a.mt[i][j]%MOD)*(b.mt[j][k]%MOD);
res.mt[i][k]%=MOD;
}
}
return res;
}
MT Mi(MT a,int b)
{
if(b==1)
return a;
MT t=Mi(a,b/2);
MT tmp=Mult(t,t);
if(b%2==1)
return Mult(a,tmp);
else return tmp;
}
void BuildStartMatrix(MT &start)
{
int i,j;
for(i=0;i<idx;i++)
{
if(T[i]->isdanger==0)
{
for(j=0;j<4;j++)
{
if(T[i]->next[j]->isdanger==0)
start.mt[i][T[i]->next[j]->num]++;
}
}
}
}
int n,m;
char ss[11];
int main()
{
int i,j,k;
scanf("%d%d",&m,&n);
Init();
while(m--)
{
scanf("%s",ss);
Insert(ss);
}
BuildTrie();
MT start;
BuildStartMatrix(start);
MT res=Mi(start,n);
int ans=0;
for(i=0;i<idx;i++)
{
ans+=res.mt[0][i];
ans%=MOD;
}
printf("%d\n",ans);
return 0;
}
静态版本
静态版本
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MOD=100000;
//******************************************Trie部分********************************************
struct Trie
{
int fail;
int next[4];
bool isdanger;
void init()
{
memset(next,-1,sizeof(next));
fail=-1;
isdanger=0;
}
}T[10000];
int root;
int idx=0;
void Init()
{
idx=0;
T[idx].init();
root=idx;
idx++;
}
int id(char s)
{
switch(s)
{
case 'A': return 0;
case 'T': return 1;
case 'G': return 2;
case 'C': return 3;
}
}
void Insert(char *s)
{
int j;
int r=root;
for(j=0;j<strlen(s);j++)
{
int i=id(s[j]);
if(T[r].next[i]==-1)
{
T[idx].init();
T[r].next[i]=idx;
idx++;
}
r=T[r].next[i];
}
T[r].isdanger=1;
}
void BuildTrie()
{
int r=root,p;
queue<int >q;
T[root].fail=root;
T[root].isdanger=0;
q.push(root);
while(!q.empty())
{
p=q.front();
q.pop();
T[p].isdanger=T[p].isdanger||T[T[p].fail].isdanger;
for(int i=0;i<4;i++)
{
if(T[p].next[i]==-1)
{
if(p==root)
T[p].next[i]=root;
else
T[p].next[i]=T[T[p].fail].next[i];
}
else
{
if(p==root)
T[T[p].next[i]].fail=root;
else
T[T[p].next[i]].fail=T[T[p].fail].next[i];
q.push(T[p].next[i]);
}
}
}
}
//******************************************矩阵乘法部分**********************************
struct MT
{
__int64 mt[110][110];
};
MT Mult(MT a,MT b)
{
int i,j,k;
MT res;
memset(res.mt,0,sizeof(res.mt));
for(i=0;i<idx;i++)
for(j=0;j<idx;j++)
if(a.mt[i][j])
{
for(k=0;k<idx;k++)
{
res.mt[i][k]+=(a.mt[i][j]%MOD)*(b.mt[j][k]%MOD);
res.mt[i][k]%=MOD;
}
}
return res;
}
MT Mi(MT a,int b)
{
if(b==1)
return a;
MT t=Mi(a,b/2);
MT res=Mult(t,t);
if(b%2==1)
return Mult(a,res);
else return res;
}
void BuildStartMatrix(MT &start)
{
int i,j;
for(i=0;i<idx;i++)
{
if(T[i].isdanger==0)
{
for(j=0;j<4;j++)
{
if(T[T[i].next[j]].isdanger==0)
start.mt[i][T[i].next[j]]++;
}
}
}
}
int n,m;
char ss[11];
int main()
{
int i,j,k;
scanf("%d%d",&m,&n);
Init();
while(m--)
{
scanf("%s",ss);
Insert(ss);
}
BuildTrie();
MT start;
BuildStartMatrix(start);
MT res=Mi(start,n);
int ans=0;
for(i=0;i<idx;i++)
{
ans+=res.mt[0][i];
ans%=MOD;
}
printf("%d\n",ans);
return 0;
}
POJ 2778#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MOD=100000;
//******************************************Trie部分********************************************
struct Trie
{
Trie *fail;
Trie *next[4];
bool isdanger;
int num;
Trie()
{
memset(next,NULL,sizeof(next));
fail=NULL;
isdanger=0;
}
}*root,*T[10000];
int idx=0;
void NewTrie()
{
T[idx]=new Trie();
T[idx]->num=idx;
}
void Init()
{
idx=0;
NewTrie();
root=T[idx++];
}
int id(char s)
{
switch(s)
{
case 'A': return 0;
case 'T': return 1;
case 'G': return 2;
case 'C': return 3;
}
}
void Insert(char *s)
{
int j;
Trie *r=root;
for(j=0;j<strlen(s);j++)
{
int i=id(s[j]);
if(r->next[i]==NULL)
{
NewTrie();
r->next[i]=T[idx++];
}
r=r->next[i];
}
r->isdanger=1;
}
void BuildTrie()
{
Trie *r=root,*p;
queue<Trie *>q;
root->fail=root;
root->isdanger=0;
q.push(root);
while(!q.empty())
{
p=q.front();
q.pop();
p->isdanger=p->isdanger||p->fail->isdanger;
for(int i=0;i<4;i++)
{
if(p->next[i]==NULL)//如果p->next[i]为空，则赋值为p的后缀的next[i]
{
if(p==root)
p->next[i]=root;
else
p->next[i]=p->fail->next[i];
}
else //如果p->next[i]不为空，则构造后缀(失败)节点
{
if(p==root)
p->next[i]->fail=root;
else
p->next[i]->fail=p->fail->next[i];
q.push(p->next[i]);
}
}
}
}
//******************************************矩阵乘法部分**********************************
struct MT
{
__int64 mt[110][110];
};
MT Mult(MT a,MT b)
{
int i,j,k;
MT res;
memset(res.mt,0,sizeof(res.mt));
for(i=0;i<idx;i++)
for(j=0;j<idx;j++)
if(a.mt[i][j])//矩阵乘法优化
{
for(k=0;k<idx;k++)
{
res.mt[i][k]+=(a.mt[i][j]%MOD)*(b.mt[j][k]%MOD);
res.mt[i][k]%=MOD;
}
}
return res;
}
MT Mi(MT a,int b)
{
if(b==1)
return a;
MT t=Mi(a,b/2);
MT tmp=Mult(t,t);
if(b%2==1)
return Mult(a,tmp);
else return tmp;
}
void BuildStartMatrix(MT &start)
{
int i,j;
for(i=0;i<idx;i++)
{
if(T[i]->isdanger==0)
{
for(j=0;j<4;j++)
{
if(T[i]->next[j]->isdanger==0)
start.mt[i][T[i]->next[j]->num]++;
}
}
}
}
int n,m;
char ss[11];
int main()
{
int i,j,k;
scanf("%d%d",&m,&n);
Init();
while(m--)
{
scanf("%s",ss);
Insert(ss);
}
BuildTrie();
MT start;
BuildStartMatrix(start);
MT res=Mi(start,n);
int ans=0;
for(i=0;i<idx;i++)
{
ans+=res.mt[0][i];
ans%=MOD;
}
printf("%d\n",ans);
return 0;
}
静态版本
静态版本#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MOD=100000;
//******************************************Trie部分********************************************
struct Trie
{
int fail;
int next[4];
bool isdanger;
void init()
{
memset(next,-1,sizeof(next));
fail=-1;
isdanger=0;
}
}T[10000];
int root;
int idx=0;
void Init()
{
idx=0;
T[idx].init();
root=idx;
idx++;
}
int id(char s)
{
switch(s)
{
case 'A': return 0;
case 'T': return 1;
case 'G': return 2;
case 'C': return 3;
}
}
void Insert(char *s)
{
int j;
int r=root;
for(j=0;j<strlen(s);j++)
{
int i=id(s[j]);
if(T[r].next[i]==-1)
{
T[idx].init();
T[r].next[i]=idx;
idx++;
}
r=T[r].next[i];
}
T[r].isdanger=1;
}
void BuildTrie()
{
int r=root,p;
queue<int >q;
T[root].fail=root;
T[root].isdanger=0;
q.push(root);
while(!q.empty())
{
p=q.front();
q.pop();
T[p].isdanger=T[p].isdanger||T[T[p].fail].isdanger;
for(int i=0;i<4;i++)
{
if(T[p].next[i]==-1)
{
if(p==root)
T[p].next[i]=root;
else
T[p].next[i]=T[T[p].fail].next[i];
}
else
{
if(p==root)
T[T[p].next[i]].fail=root;
else
T[T[p].next[i]].fail=T[T[p].fail].next[i];
q.push(T[p].next[i]);
}
}
}
}
//******************************************矩阵乘法部分**********************************
struct MT
{
__int64 mt[110][110];
};
MT Mult(MT a,MT b)
{
int i,j,k;
MT res;
memset(res.mt,0,sizeof(res.mt));
for(i=0;i<idx;i++)
for(j=0;j<idx;j++)
if(a.mt[i][j])
{
for(k=0;k<idx;k++)
{
res.mt[i][k]+=(a.mt[i][j]%MOD)*(b.mt[j][k]%MOD);
res.mt[i][k]%=MOD;
}
}
return res;
}
MT Mi(MT a,int b)
{
if(b==1)
return a;
MT t=Mi(a,b/2);
MT res=Mult(t,t);
if(b%2==1)
return Mult(a,res);
else return res;
}
void BuildStartMatrix(MT &start)
{
int i,j;
for(i=0;i<idx;i++)
{
if(T[i].isdanger==0)
{
for(j=0;j<4;j++)
{
if(T[T[i].next[j]].isdanger==0)
start.mt[i][T[i].next[j]]++;
}
}
}
}
int n,m;
char ss[11];
int main()
{
int i,j,k;
scanf("%d%d",&m,&n);
Init();
while(m--)
{
scanf("%s",ss);
Insert(ss);
}
BuildTrie();
MT start;
BuildStartMatrix(start);
MT res=Mi(start,n);
int ans=0;
for(i=0;i<idx;i++)
{
ans+=res.mt[0][i];
ans%=MOD;
}
printf("%d\n",ans);
return 0;
}
