Design password
Now you need to design a password
S
，
S
S，S
S. S needs to meet:
S The length of the is N； S Contains only lowercase English letters; S Contains no substrings T；
For example: a b c abc abc and a b c d e abcde abcde yes a b c d e abcde Substring of abcde, a b d abd abd is not a b c d e abcde Substring of abcde.
How many different passwords meet the requirements?
(as the answer will be very large, please output the answer module 1 e 9 + 7 1e9+7 The remainder of 1e9+7.)
Input format
Enter an integer on the first line
N
N
N. Indicates the length of the password.
The second line is the input string T ， T T，T T. T contains only lowercase letters.
Output format
Output a positive integer representing the digital analog of the total scheme
1
e
9
+
7
1e9+7
Results after 1e9+7.
Data range
1
≤
N
≤
50
1≤N≤50
1≤N≤50,
1
≤
∣
T
∣
≤
N
1≤|T|≤N
1≤∣T∣≤N，
∣
T
∣
|T|
∣ T ∣ yes
T
T
Length of T.
This topic is the combination of DP and KMP. The specific state design is:
f
[
i
]
[
j
]
:
structure
make
Yes
front
i
individual
word
mother
，
And
When
front
word
mother
yes
strand
T
of
shape
state
yes
j
，
(
this
individual
shape
state
finger
of
yes
T
of
K
M
P
of
n
e
x
t
number
group
)
f[i][j]: the first I letters are constructed, and the status of the current letter pair string t is j, \ \ (this status refers to the next array of KMP of T)
f[i][j]: the first I letters are constructed, and the state of the current letter pair string t is j, (this state refers to the next array of KMP of T)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 55, mod = 1e9 + 7;
int n, m;
int f[N][N];
//f[i][j] represents all schemes with the first I letters and the state of string T is j
char T[N];
int ne[N];
int main()
{
cin >> n >> T + 1;
m = strlen(T + 1);
//Find the next array of T
for(int i = 2, j = 0; i <= m; i++)
{
while(j && T[i] != T[j + 1]) j = ne[j];
if(T[i] == T[j + 1]) j++;
ne[i] = j;
}
f[0][0] = 1; //When the length is 0, the status is 0. There is only one scheme
for(int i = 0; i <= n; i++) //Enumeration length
for(int j = 0; j <= m; j++)//Enumeration status
for(char k = 'a'; k <= 'z'; k++) //Enumerate the next letter
{
int u = j;
while(u && k != T[u + 1]) u = ne[u];
//Find the state after transfer in the next array
if(k == T[u + 1]) u++;
if(u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
//If the status is legal, dp will be transferred. Legal means that the number of currently matched letters u is less than m
}
int res = 0;
for(int i = 0; i < m; i++) res = (res + f[n][i]) % mod;
cout << res << endl;
return 0;
}
Text generator
Title Description
JSOI gave team member ZYX a task to compile a computer software called "text generator": the users of the software are some young people, and they are now using version v6 of GW text generator.
The software can generate some articles randomly - always a fixed length and completely random article. That is, each character in the generated article is completely random. If an article contains at least one word that users know, then we say the article is readable (we call it an article) s s s contains words t t t. If and only if the word t t t is an article s s s). However, even according to such standards, the articles generated by the v6 version of GW text generator currently used by users are almost completely unreadable. ZYX needs to indicate the number of readable texts in all texts generated by GW text generator v6 in order to successfully obtain v7 update. Can you help him?
The answer is right 1 0 4 + 7 10^4 + 7 104 + 7 take mold.
Input format
The first line has two integers, representing the total number of words understood by the user
n
n
n and generated article length
m
m
m.
next
n
n
n lines, one string per line
s
i
s_i
si, represents a word understood by the user.
Output format
Output an integer on a line to represent the answer pair
1
0
4
+
7
10^4 + 7
Results of 104 + 7 mold taking.
The last question is that the construction length is
n
n
The number of strings that are n and do not contain a given substring.
The problem is that the construction length is
n
n
The number of strings that are n and do not contain multiple given substrings
This question is the AC automata version of the previous question, and the state design is also similar to the previous question:
f
[
i
]
[
j
]
:
long
degree
yes
i
，
stay
a
c
since
move
machine
upper
of
shape
state
yes
j
of
place
yes
no
package
contain
to
set
single
Words
of
word
symbol
strand
of
individual
number
f[i][j]: the number of strings with length I and state j on ac automata that do not contain a given word
f[i][j]: the number of strings with length I and state j on ac automata that do not contain a given word
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int N = 110, M = 6010, Mod = 10007;
int n, m, f[N][M]; //f[i][j]: the number of strings with length I and state j on ac automata that do not contain a given word
int idx, tr[M][26], ne[M];
bool have[M];
char str[N];
void insert()
{
int p = 0;
for(int i = 0; str[i]; i ++)
{
int t = str[i] - 'A';
if(!tr[p][t]) tr[p][t] = ++ idx;
p = tr[p][t];
}
have[p] = true;
}
int q[M];
void build()
{
int hh = 0, tt = -1;
for(int i = 0; i < 26; i ++)
if(tr[0][i]) q[++ tt] = tr[0][i];
while(hh <= tt)
{
int u = q[hh ++];
for(int i = 0; i < 26; i ++)
{
int &p = tr[u][i];
if(!p) p = tr[ne[u]][i];
else
{
ne[p] = tr[ne[u]][i];
q[++ tt] = p;
have[p] |= have[ne[p]];
}
}
}
}
int main()
{
#ifdef LOCAL
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
cin >> n >> m;
for(int i = 0; i < n; i ++)
{
cin >> str;
insert();
}
build();
f[0][0] = 1;
for(int i = 0; i < m; i ++) //Enumeration length
for(int j = 0; j <= idx; j ++) //Enumeration status
for(int k = 0; k < 26; k ++) //What's next
{
int p = tr[j][k];
if(!have[p]) f[i + 1][p] = (f[i + 1][p] + f[i][j]) % Mod;
//If the state is legal, dp will be transferred. Legal means that there is no string ending at p
}
int ans = 1;
for(int i = 0; i < m; i ++) ans = (ans * 26) % Mod;
for(int i = 0; i <= idx; i ++) ans = (ans - f[m][i] + Mod) % Mod;
cout << ans << endl;
return 0;
}