# meaning of the title

Give \ (n \) strings, and construct a string \ (S \) with a length of \ (m \), so that at least one of the given \ (n \) strings is a substring of \ (S \). Ask about the number of options.

# thinking

\(AC \) automaton + \ (DP \)
Consider that at least one of the substrings is S. Consider subtracting all the cases that do not contain any strings.
The whole situation is \ (26^m \), and then consider how to find out the situation without any strings.
Use \ (f[i][j] \) to indicate that \ (I \) characters have been determined, and now it is the number of schemes at position j of \ (AC \) automaton.
Obviously, if the \ (j \) position is the end of the given string or you can jump to the end of the given string along the \ (fail \) pointer, you cannot transfer. Others can be transferred to \ (f[i + 1][k] \). \(K \) is a son of \ (j \) on \ (AC \) automata.
The final answer is \ (26 ^ m - \ sum \ limits {I = 0} ^ {tot} f [M] [i] (I is not giving the end of the string) \)

# Code

```/*
* @Author: wxyww
* @Date:   2019-02-01 19:33:15
*/
#include<cstring>
#include<queue>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 6000 + 10,mod = 10007;
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
char s[110];
queue<int>q;
int trie[N][27],bz[N],fail[N],tot;
void ins() {
int len = strlen(s + 1);
int now = 0;
for(int i = 1;i <= len;++i) {
int x = s[i] - 'A';
if(!trie[now][x]) trie[now][x] = ++tot;
now = trie[now][x];
}
bz[now] = 1;
}
void get_fail() {
for(int i = 0;i < 26;++i) if(trie[0][i]) q.push(trie[0][i]);
while(!q.empty()) {
int u = q.front();q.pop();
bz[u] |= bz[fail[u]];
for(int i = 0;i < 26;++i) {
if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i],q.push(trie[u][i]);
else trie[u][i] = trie[fail[u]][i];
}
}
}
int qm(int x,int y) {
int ans = 1;
for(;y;y >>= 1,x = 1ll * x * x % mod) {
if(y & 1) ans = 1ll * ans * x % mod;
}
return ans;
}
int f[N][N];
int main() {
for(int i = 1;i <= n;++i) {
scanf("%s",s + 1);
ins();
}
get_fail();
f[0][0] = 1;

for(int i = 0;i < m;++i) {
for(int j = 0;j <= tot;++j) {
if(bz[j] || !f[i][j]) continue;
for(int k = 0;k < 26;++k) {
int z = trie[j][k];
f[i + 1][z] += f[i][j];
f[i + 1][z] >= mod ? f[i + 1][z] -= mod : 0;
}
}
}
int ans = qm(26,m);
for(int i = 0;i <= tot;++i) {
if(!bz[i]) ans = (ans - f[m][i] + mod) % mod;
}
cout<<ans;
return 0;
}```

Tags: C++

Posted on Tue, 03 Dec 2019 03:13:03 -0800 by Paul1893