# Batch query UPS Express Logistics the easiest way

2023-01-23   ES

## POJ 2778 DNA Sequence

Problem :Models that contain only (a, g, c, t) (M <= 10, Len <= 10), and ask all the string with (A, G, C, T) with all length n contains (A, G, C, T) How many of them contain pattern string. (n <= 2000000000)
Solution :First establish an AC automatic machine for all modes. Then DP [i] [j] indicates that the length of the length of the AC automatic machine J is to meet the number of strings such as the node j of the AC automatic machine. Operation.

``````#include <iostream>
#include <string>
#include <queue>

using namespace std;

const int N = 208;
const int mo = 100000;

int id[128];

struct Matrix
{
int n;
int a[N][N];
Matrix(int n_, int p)
{
n = n_;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
{
a[i][j] = 0;
if (i == j) a[i][j] = p;
}
}
friend Matrix operator *(Matrix A, Matrix B)
{
Matrix C(A.n, 0);
for (int i = 0; i < A.n; ++i)
for (int j = 0; j < A.n; ++j)
for (int k = 0; k < A.n; k++)
C.a[i][j] = (C.a[i][j] + 1ll * A.a[i][k] * B.a[k][j] % mo) % mo;
return C;
}
void print()
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j) cout << a[i][j] << " ";
cout << endl;
}
}
};

struct AC_Automan
{
int next[N][4];
int fail[N];
int cnt[N];
int root, tot;

int newnode()
{
for (int i = 0; i <= 3; ++i) next[tot][i] = -1;
fail[tot] = cnt[tot] = -1;
}
void clear()
{
tot = 0;
root = newnode();
}
void insert(const string &s)
{
int p = root;
for (int i = 0, len = s.length(); i < len; ++i)
{
if (next[p][id[s[i]]] == -1) next[p][id[s[i]]] = newnode();
p = next[p][id[s[i]]];
}
cnt[p] = 1;
}
void build()
{
queue <int> Q;
Q.push(root);
while (!Q.empty())
{
int p = Q.front(); Q.pop();
for (int i = 0; i < 4; ++i)
{
if (~next[p][i])
{
if (p == root) fail[next[p][i]] = root;
else fail[next[p][i]] = next[fail[p]][i];
Q.push(next[p][i]);
}
else
{
if (p == root) next[p][i] = root;
else next[p][i] = next[fail[p]][i];
}
}
}
}
Matrix power(Matrix A, int y)
{
Matrix B(tot, 1);
while (y)
{
if (y & 1) B = B * A;
A = A * A;
y >>= 1;
}
return B;
}

void solve(int num)
{
Matrix A(tot, 0);
for (int i = 0; i <= tot; ++i)
{
for (int j = 0; j < 4; ++j)
{
int flag = 1;
for (int temp = next[i][j]; temp != root; temp = fail[temp])
{
if (~cnt[temp]) flag = 0;
}
A.a[i][next[i][j]] += flag;
}
}
A = power(A, num);
int ans = 0;
for (int i = 0; i < tot; ++i) ans = (ans + A.a[0][i]) % mo;
cout << ans << endl;
}
}ac;

int main()
{
cin.sync_with_stdio(0);
id['A'] = 0; id['G'] = 1; id['C'] = 2; id['T'] = 3;
int m, n;
while (cin >> m >> n)
{
ac.clear();
for (int i = 1; i <= m; ++i)
{
string s; cin >> s;
ac.insert(s);
}
ac.build();
ac.solve(n);
}
}
``````

Reprinted: https://www.cnblogs.com/rpsebastian/p/7193485.html

source