#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define N 105
using namespace std;
struct tree{
tree *next[4], *fail;
int flag, num;
}*root, *p;
tree arr[1000];
int indexx;
int map(char ch){
if(ch == 'A') return 0;
if(ch == 'C') return 1;
if(ch == 'T') return 2;
if(ch == 'G') return 3;
}
void newn(){
arr[indexx].flag = 0;
arr[indexx].num = indexx;
for(int i = 0; i < 4; i ++){
arr[indexx].next[i] = 0;
}
}
void init(){
indexx = 0;
newn();
root = &arr[indexx++];
}
void insert(char ch[], int w){
int t, i = 0;
p = root;
while(ch[i]){
t = map(ch[i]);
if(p->next[t]==0){
newn();
p->next[t] = &arr[indexx++];
}
p = p->next[t];
i ++;
}
p->flag = w;
}
tree *que[10000];
bool search(tree *q)
{
while(q != root)
{
if(q->flag) return true;
q = q->fail;
}
return false;
}
void get_fail(){
p=root;
p->fail = root;
int open = 0, close = -1, i;
que[0] = p;
while(close < open){
p = que[++ close];
tree *q = p;
int pass = 0;
if(q->flag == 0) pass = search(q);
if(pass) p->flag = 1;
for(i = 0; i < 4; i ++)
{
if(p->next[i] == 0){
if(p == root) p->next[i] = root;
else p->next[i] = p->fail->next[i];
}
else{
if(p == root) p->next[i]->fail = root;
else p->next[i]->fail = p->fail->next[i];
que[++open] = p->next[i];
}
}
}
}
long long n;
int m;
long long f[N][N];
#define M 100000
void mod_multi(long long a[N][N], long long b[N][N], int r){//A=A*B%M A為r*r矩陣
int i, j, k;
long long c[N][N] = {};
for (k = 0; k < r; k++)
for (i = 0; i < r; i++)
for (j = 0; j < r; j++){
c[i][j] += a[i][k] * b[k][j];
c[i][j] %= M;
}
for (i = 0; i < r; i++)
for (j = 0; j < r; j++)
a[i][j] = c[i][j];
}
void mod_exp(long long a[N][N], long long n, int r){//A=A^n%m A為r*r矩陣
int i, j, k;
long long ans[N][N] = {};
for (i = 0; i < r; i++)ans[i][i] = 1; //單位陣
for (; n; n >>= 1){
if (n & 1)
mod_multi(ans, a, r);
mod_multi(a, a, r);
}
for (i = 0; i < r; i++)
for (j = 0; j < r; j++)
a[i][j] = ans[i][j];
}
int main(){
while(scanf("%d %lld", &m, &n) != EOF){
init();
char str[12];
for(int i = 0; i < m; i ++){
scanf("%s", str);
insert(str, 1);
}
get_fail();
memset(f, 0, sizeof(f));
for(int i = 0; i < indexx; i ++){
for(int j = 0; j < 4; j ++){
if(arr[i].next[j]->flag == 0 && arr[i].flag == 0)
f[i][arr[i].next[j]->num] ++;
}
}
mod_exp(f, n, indexx);
long long ans = 0;
for(int i = 0; i < indexx; i ++){
ans += f[0][i];
ans %= M;
}
printf("%lld\n", ans);
}
}
另一個(gè)版本的比之高效很多
#include <stdio.h>
#include <string.h>
#define R 5
#define N 105
#define M 100000
typedef long long LL;
int tree[N][R], flag[N], fail[N], state;
int cha[128] = {};
void init(){
cha['A'] = 1; cha['T'] = 2;
cha['G'] = 3; cha['C'] = 4;
memset(tree, -1, sizeof(tree));
memset(flag, 0, sizeof(flag));
memset(fail, -1, sizeof(fail));
flag[0] = 0;
state = 1;
}
void insert(char ch[]) {
int p = 0, i = 0, t;
while(ch[i]) {
t = cha[ch[i]];
if(tree[p][t] < 0) {
flag[state] = 0;
tree[p][t] = state++;
}
p = tree[p][t];
i ++;
}
flag[p] = 1;
}
int que[N];
void get_fail() {
int close = -1, open = 0;
que[0] = 0;
fail[0] = 0;
while(close < open) {
int p = que[++close];
for(int i = 0; i < R; i ++) {
if(tree[p][i] == -1){
if(p == 0) tree[p][i] = 0;
else tree[p][i] = tree[fail[p]][i];
} else {
if(p == 0) fail[tree[p][i]] = 0;
else fail[tree[p][i]] = tree[fail[p]][i];
que[++open] = tree[p][i];
}
}
}
}
int n, L;
LL f[N][N], sum = 0;
void mod_multi(LL a[N][N], LL b[N][N], int r){
int i, j, k;
LL c[N][N] = {};
for (k = 0; k < r; k++)
for (i = 0; i < r; i++)
if(a[i][k])
for (j = 0; j < r; j++){
c[i][j] += a[i][k] * b[k][j];
c[i][j] %= M;
}
for (i = 0; i < r; i++)
for (j = 0; j < r; j++)
a[i][j] = c[i][j];
}
void mod_exp(LL a[N][N], LL n, int r){
int i, j, k;
LL ans[N][N] = {};
for (i = 0; i < r; i++)ans[i][i] = 1;
for (; n; n >>= 1){
if (n & 1)
mod_multi(ans, a, r);
mod_multi(a, a, r);
}
for (i = 0; i < r; i++)
for (j = 0; j < r; j++)
a[i][j] = ans[i][j];
}
LL fast(LL sum, int L) {
LL temp = 1ll;
for(;L;L >>= 1) {
if(L&1) {
temp *= sum;
temp %= M;
}
sum *= sum;
sum %= M;
}
return temp;
}
bool search(int q) {
while(q != 0) {
if(flag[q]) return true;
q = fail[q];
}
return false;
}
int main() {
while(scanf("%d %d", &n ,&L) != EOF) {
char str[11];
init();
for(int i = 0; i < n; i ++) {
scanf("%s", str);
insert(str);
}
get_fail();
int map[N], cnt = 0, t;
memset(map,-1,sizeof(map));
memset(f, 0, sizeof(f));
for(int i = 0; i < state; i ++) {
if(flag[i] == 0) flag[i] = search(i);
}
for(int i = 0; i < state; i ++) {
if(flag[i]==0)
for(int j = 1; j < R; j ++) {
if(flag[tree[i][j]] == 0) {
t = tree[i][j];
if(map[i] == -1) map[i] = cnt ++;
if(map[t] == -1) map[t] = cnt ++;
f[map[i]][map[t]] ++;
}
}
}
mod_exp(f, L, cnt);
LL ans = 0;
for(int i = 0; i < cnt; i ++) {
ans += f[0][i];
ans %= M;
}
printf("%lld\n", ans);
}
}