最近研究data矩阵，稍微总结一下，以后继续补充：
ac自动机处理字符串，dp计算谜底，用矩阵来减速
每日一道理
巴尔扎克说过“不幸，是天才的进升阶梯，信徒的洗礼之水，弱者的无底深渊”。风雨过后，眼前会是鸥翔鱼游的天水一色；走出荆棘，前面就是铺满鲜花的康庄大道；登上山顶，脚下便是积翠如云的空蒙山色。 在这个世界上，一星陨落，黯淡不了星空灿烂，一花凋零，荒芜不了整个春天。人生要尽全力度过每一关，不管遇到什么困难不可轻言放弃。
巴尔扎克说过“不幸，是天才的进升阶梯，信徒的洗礼之水，弱者的无底深渊”。风雨过后，眼前会是鸥翔鱼游的天水一色；走出荆棘，前面就是铺满鲜花的康庄大道；登上山顶，脚下便是积翠如云的空蒙山色。 在这个世界上，一星陨落，黯淡不了星空灿烂，一花凋零，荒芜不了整个春天。人生要尽全力度过每一关，不管遇到什么困难不可轻言放弃。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const long long mod=100000;
struct
{
int next[30],tmp,fail,lon;
}trie[111];
int lon;
int m,n;
struct matrix
{
long long data[111][111];
int size;
matrix(int tmp,int lon)
{
size=lon;
for(int i=0;i<=size;i++)
for(int j=0;j<=size;j++)
data[i][j]=tmp;
}
matrix operator * (const matrix &xx) const
{
matrix ans(0,size);
for(int p=0;p<=size;p++)
for(int q=0;q<=size;q++)
for(int i=0;i<=size;i++)
{
ans.data[p][q]+=data[p][i]*xx.data[i][q];
ans.data[p][q]%=mod;
}
return(ans);
}
};
void trieini()
{
memset(trie,0,sizeof(trie));
lon=0;
}
void insert(char s[])
{
int t=0;
int n=strlen(s+1);
for(int i=1;i<=n;i++)
{
if(trie[t].next[s[i]-'A']==0)
{
trie[t].next[s[i]-'A']=++lon;
trie[lon].lon=i;
}
t=trie[t].next[s[i]-'A'];
if(i==n)
trie[t].tmp++;
}
} void getfail()
{
int root=0;
queue <int> q;
q.push(root);
trie[root].fail=root;
while(!q.empty())
{
int t=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(trie[t].next[i])
{
if(t==root)
{
int u=trie[t].next[i];
trie[u].fail=root;
q.push(u);
continue;
}
int u=trie[t].next[i];
int tmp=trie[t].fail;
while(tmp!=root&&trie[tmp].next[i]==0)
tmp=trie[tmp].fail;
if(trie[tmp].next[i])
trie[u].fail=trie[tmp].next[i];
else
trie[u].fail=root;
q.push(u);
}
}
}
for(int i=1;i<=lon;i++)
{
int t=i;
while(t!=root)
{
int u=trie[t].fail;
trie[t].tmp+=trie[u].tmp;
t=u;
}
}
} void find(matrix &a)
{
int root=0;
for(int k=0;k<=lon;k++)
{
if(trie[k].tmp) continue;
for(int i=0;i<26;i++)
{
if(i+'A'!='A')
if(i+'A'!='C')
if(i+'A'!='T')
if(i+'A'!='G')
continue;
int t=k;
while(t!=root&&trie[t].next[i]==0)
t=trie[t].fail; if(trie[t].next[i])
{
int u=trie[t].next[i];
if(!trie[u].tmp)
a.data[k][u]++;
}
else
a.data[k][0]++;
}
}
} int main()
{
while(scanf("%d %d",&m,&n)!=EOF)
{
trieini();
char s[15];
for(int i=1;i<=m;i++)
{
scanf("%s",s+1);
insert(s);
}
getfail();
matrix a(0,lon);
find(a);
matrix ans(a);
n--;
while(n)
{
if(n&1)
ans=ans*a;
a=a*a;
n/=2;
}
int answer=0;
for(int i=0;i<=lon;i++)
{
answer+=ans.data[0][i];
answer%=mod;
}
cout<<answer<<endl;
}
return 0;
}
文章结束给大家分享下程序员的一些笑话语录： IBM和波音777
波音777是有史以来第一架完全在电脑虚拟现实中设计制造的飞机，所用的设备完全由IBM公司所提供。试飞前，波音公司的总裁非常热情的邀请IBM的技术主管去参加试飞，可那位主管却说道:“啊，非常荣幸，可惜那天是我妻子的生日，So..”..
波音公司的总载一听就生气了:“胆小鬼，我还没告诉你试飞的日期呢!”
---------------------------------
原创文章 By
data和矩阵
---------------------------------