Problem Links
P4052 [JSOI2007] Text Generator P3311 [SDOI2014] Counting Numbers P2292 [HNOI2004] L Language (Data Strengthened)
[JSOI2007] Text Generator
We apply dynamic programming (DP) to count the number of valid strings.
It is clear that we can use a complement set transformation. Let the total number of invalid strings be (total), then (Result = 26^m - total).
Define (dp(i, j)) as the maximum value when constructing a string of length (i) ending at node (j) in the AC automaton.
First, construct the Trie structure. If no matches occur in the string, we have: [ dp(i, Trie_transition[j]) = \sum dp(i-1, j) ]
The final result for invalid strings is: [ total = \sum dp(m, i) ]
Now, the challenge reduces to determining whether a string fails to match any patterns.
A key observation: if any suffix of a string matches a pattern, it is considered valid.
To handle this, during the construction of the Trie, maintain an array (valid[i]) indicating whether the string up to node (i) matches any pattern.
If a node represents the end of a pattern, set (valid[i] = true).
The transition rule is: [ valid[i] = valid[i] \lor valid[fail_link[i]] ]
Code (C++)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 3, M = 103, Mod = 1e4 + 7;
namespace ACAutomaton {
int trie[N][26], failLink[N], nodeCount = 0;
bool isValid[N];
long long dp[M][N];
void insert(const string& s) {
int current = 0;
for(char c : s) {
int index = c - 'A';
if(!trie[current][index]) trie[current][index] = ++nodeCount;
current = trie[current][index];
}
isValid[current] = true;
}
void build() {
queue<int> q;
for(int i = 0; i < 26; ++i) {
if(trie[0][i]) {
q.push(trie[0][i]);
failLink[trie[0][i]] = 0;
} else {
trie[0][i] = 0;
}
}
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < 26; ++i) {
if(trie[u][i]) {
failLink[trie[u][i]] = trie[failLink[u]][i];
isValid[trie[u][i]] |= isValid[failLink[trie[u][i]]];
q.push(trie[u][i]);
} else {
trie[u][i] = trie[failLink[u]][i];
}
}
}
}
long long solve(int length) {
dp[0][0] = 1;
for(int i = 1; i <= length; ++i) {
for(int j = 0; j <= nodeCount; ++j) {
if(dp[i-1][j] == 0) continue;
for(int k = 0; k < 26; ++k) {
int nextNode = trie[j][k];
if(!isValid[nextNode]) {
dp[i][nextNode] = (dp[i][nextNode] + dp[i-1][j]) % Mod;
}
}
}
}
long long result = 1;
for(int i = 0; i < length; ++i) result = (result * 26) % Mod;
for(int i = 0; i <= nodeCount; ++i) result = (result - dp[length][i] + Mod) % Mod;
return result;
}
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; ++i) {
string s;
cin >> s;
ACAutomaton::insert(s);
}
ACAutomaton::build();
cout << ACAutomaton::solve(m) << endl;
return 0;
}
[SDOI2014] Counting Numbers
This problem uses digit DP with AC automaton handling similar to the previous one.
Core Code
long long dp_table[20][10000][2][2]; // dp(digit, pos, limit, leading_zero)
long long digit_dp(int digit, int pos, bool limit, bool leading_zero) {
if(digit < 0) return !ACAutomaton::isValid[pos];
if(ACAutomaton::isValid[pos]) return 0;
if(dp_table[digit][pos][limit][leading_zero] != -1)
return dp_table[digit][pos][limit][leading_zero];
int upperBound = limit ? (n[digit] - '0') : 9;
long long result = 0;
for(int i = 0; i <= upperBound; ++i) {
int nextPos = leading_zero && i == 0 ? 0 : ACAutomaton::trie[pos][i];
result += digit_dp(digit - 1, nextPos, limit && (upperBound == i), leading_zero && i == 0);
}
return dp_table[digit][pos][limit][leading_zero] = result;
}
Note: The DP directly counts one extra case where the number is zero, so subtract one from the final answer.
[HNOI2004] L Language
We apply state compression DP here since the size of the string is small.
Define (status[i]) as the state in the Trie structure, where each bit indicates whether a specific pattern ends at that position.
We perform DP using a state (f), where (f[i]) indicates whether the last (i) characters form a valid prefix.
If (f \cap status[i] \neq \emptyset), set the first bit of (f) to 1. Shift the state (f) left by one bit for each character processed.
Code (C++)
#include <bits/stdc++.h>
using namespace std;
const int MAXL = 2e6 + 3, MAXN = 203;
namespace ACAutomaton {
int trie[MAXN][26], failLink[MAXN];
unsigned mask[MAXN];
bool isPatternEnd[MAXN];
void insert(const string& s) {
int current = 0;
for(char c : s) {
int index = c - 'a';
if(!trie[current][index]) trie[current][index] = ++nodeCount;
current = trie[current][index];
}
isPatternEnd[current] = true;
}
void build() {
queue<pair<int, int>> q;
for(int i = 0; i < 26; ++i) {
if(trie[0][i]) {
q.push({trie[0][i], 1});
failLink[trie[0][i]] = 0;
} else {
trie[0][i] = 0;
}
}
while(!q.empty()) {
auto [u, depth] = q.front(); q.pop();
mask[u] = mask[failLink[u]];
if(isPatternEnd[u]) mask[u] |= (1u << depth);
for(int i = 0; i < 26; ++i) {
if(trie[u][i]) {
failLink[trie[u][i]] = trie[failLink[u]][i];
q.push({trie[u][i], depth + 1});
} else {
trie[u][i] = trie[failLink[u]][i];
}
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; ++i) {
string s;
cin >> s;
ACAutomaton::insert(s);
}
ACAutomaton::build();
for(int i = 0; i < m; ++i) {
string T;
cin >> T;
int current = 0;
unsigned f = 1;
int maxLength = 0;
for(char c : T) {
int index = c - 'a';
current = ACAutomaton::trie[current][index];
f <<= 1;
if(ACAutomaton::mask[current] & f) {
f |= 1;
maxLength = max(maxLength, (int)f.bit_count());
}
}
cout << maxLength << endl;
}
return 0;
}