【★】Censored!（Forbidden Words）

发表于   |   分类于


POJ 1625

Censored! Time Limit: 5000MS Memory Limit: 10000K Total Submissions: 1859 Accepted: 489

Description

The alphabet of Freeland consists of exactly N letters. Each sentence of Freeland language (also known as Freish) consists of exactly M letters without word breaks. So, there exist exactly N^M different Freish sentences.

But after recent election of Mr. Grass Jr. as Freeland president some words offending him were declared unprintable and all sentences containing at least one of them were forbidden. The sentence S contains a word W if W is a substring of S i.e. exists such k >= 1 that S[k] = W[1], S[k+1] = W[2], …,S[k+len(W)-1] = W[len(W)], where k+len(W)-1 <= M and len(W) denotes length of W. Everyone who uses a forbidden sentence is to be put to jail for 10 years.

Find out how many different sentences can be used now by freelanders without risk to be put to jail for using it.

Input

The first line of the input file contains three integer numbers: N – the number of letters in Freish alphabet, M – the length of all Freish sentences and P – the number of forbidden words (1 <= N <= 50, 1 <= M <= 50, 0 <= P <= 10).

The second line contains exactly N different characters – the letters of the Freish alphabet (all with ASCII code greater than 32).

The following P lines contain forbidden words, each not longer than min(M, 10) characters, all containing only letters of Freish alphabet.

Output

Output the only integer number – the number of different sentences freelanders can safely use.

Sample Input

2 3 1
ab
bb

Sample Output

5

Source

Northeastern Europe 2001, Northern Subregion


此题需要建立trie，再建ac完全性的自动机（也被一些人成为trie图，一回事）。即任何状态，对应任何字符都是有转移的。如果是基本ac自动机，下面所说的动归过程中，如果碰到无法识别的转移，就需要通过回溯prefix link去获取转移到的状态。

动态规划的过程不难。

用dp[i][j]表示第i步，有多少种方式能到达j状态。

那么dp[i][j] = sigma(dp[i-1][k]) (trans[k][x] == j(x在字母表中))

用代码表示似乎简洁些

for (i = 0; i < 单词长度; i++) {
for (cur = 0; cur < 状态数; cur++) {
for each 字母k in 字母表 {
next = trans[cur][k];
if (next 不是终止状态)
dp[i+1][next] += dp[i][cur]; //(可使用滚动数组)
}
}
}

注意第4行，在非完全自动机中你需要回溯prefix link去获取转移。

最后，把所有dp[单词长度]的状态加起来。

用代码表示：

int sum = 0;

for (cur = 0; cur < 状态数; cur++) {
sum += dp[单词长度][cur];
}



// author: jfo()

////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <deque>
#include <cassert>
//#include "bigint.h"
using namespace std;


int N, M, P;
string Alphabet;
int L;
vector<string> forbidden;

int gState = 1;
int A = ‘A’; // ASCII ‘A’ -> value:65

typedef struct TrieNode {
struct TrieNode child[50];
struct TrieNode parent;
struct TrieNode fault;
int color;
} TrieNode;
TrieNode trans[101];
TrieNode root;

class BigInt
{
public:
BigInt() : m_val("0") {}
BigInt(int v)
{
do {
m_val = char(‘0’ + v % 10) + m_val;
} while(v = v / 10);
}
BigInt(const BigInt& rhs)
{
m_val = rhs.m_val;
}
const BigInt operator +=(int v)
{
return this += BigInt(v);
}
const BigInt operator +=(const BigInt& v)
{
int carry = 0;
string result;
string rhs = v.m_val;
int len = m_val.length();
int len2 = rhs.length();

if(len < len2)
m_val = string(len2 - len, ‘0’) + m_val;
else if(len > len2)
rhs = string(len - len2, ‘0’) + rhs;

len = m_val.length();
for(int i = len - 1; i >= 0; i–) {
int a = m_val[i] - ‘0’;
int b = rhs[i] - ‘0’;
int sum = a + b + carry;
result = (char)(sum % 10 + ‘0’) + result;
carry = sum >= 10 ? 1 : 0;
}
if(carry)
result = ‘1’ + result;
m_val = result;
return this;
}
const BigInt operator +(int v) const
{
return this + BigInt(v);
}
const BigInt operator +(const BigInt& rhs) const
{
BigInt tmp(this);
return tmp += (rhs);
}
operator const string() const
{
return m_val;
}
private:
string m_val;
};

typedef BigInt BIGINT;

const BigInt operator +(int v1, const BigInt& v2)
{
return v2 + v1;
}
basic_ostream<char>& operator <<(basic_ostream<char>& out, const BIGINT& v)
{
return out << (string)v;
}


//typedef RossiBigInt BIGINT;
BIGINT dp[2][sizeof(trans) / sizeof(trans[0])];

/
void input()
{
cin >> N >> M >> P;
L = min(M, 10);
cin >> Alphabet;

map<char, char> m;
for(int i = 0; i < Alphabet.length(); i++)
m[Alphabet[i]] = (char)(A + i);

string s;
int t = P;
while(t–) {
cin >> s;
for(int i = 0; i < s.length(); i++)
s[i] = m[s[i]];
forbidden.push_back(s);
}
}
/

void input()
{
char buf[51];
scanf("%d%d%d",&N,&M,&P);
scanf("%s",buf);
//Alphabet = buf;
Alphabet.clear();

map<char, char> m;
for(int i = 0; i < strlen(buf); i++) {
//m[Alphabet[i]] = (char)(A + i);
m[buf[i]] = (char)(A + i);
}

string s;
int t = P;
while(t–) {
scanf("%s",buf);
//s = buf;
s.clear();
for(int i = 0; i < strlen(buf); i++)
//s[i] = m[s[i]];
s += m[buf[i]];
forbidden.push_back(s);
}
}

void bfs(TrieNode parent)
{
if(!parent)
return;
deque<TrieNode> queue;
queue.push_front(parent);
while(!queue.empty()) {
parent = queue.back();
queue.pop_back();
for(int i = 0; i < sizeof(parent->child) / sizeof(parent->child[0]); i++) {
TrieNode child = parent->child[i];
if(!child)
continue;
TrieNode parent_fault = parent->fault;
while(parent_fault) {
if(parent_fault->child[i])
break;
parent_fault = parent_fault->fault;
}
child->fault = parent_fault ? parent_fault->child[i] : root;
queue.push_front(child);
}
}
}

void set_color(TrieNode parent)
{
if(!parent)
return;
int i, j;
for(i = 0; i < P; i++) {
TrieNode cur = parent;
for(j = 0; j < forbidden[i].length(); j++) {
int ch = forbidden[i][j] - A;
if(!cur->child[ch])
break;
cur = cur->child[ch];
}
if(j == forbidden[i].length())
cur->color = 1;
}
for(i = 0; i < sizeof(parent->child) / sizeof(parent->child[0]); i++) {
TrieNode child = parent->child[i];
if(child)
set_color(child);
}
}

void calc_trans()
{
root = &trans[0];
int i, j;
for(i = 0; i < P; i++) {
TrieNode cur = root;
int ch;
for(j = 0; j < forbidden[i].length(); j++) {
ch = forbidden[i][j] - A;
if(!cur->child[ch]) {
cur->child[ch] = &trans[gState++];
cur->child[ch]->parent = cur;
assert(gState <= 101);
}
cur = cur->child[ch];
//if(1 == cur->color)
// break;
}
cur->color = 1;
}
// root->fault = root;
bfs(root); // calculate fault ptr
set_color(root);
}

void solve()
{
int flag = 0;
calc_trans();
int state = 0;
dp[0][0] = BIGINT(1);
for(int i = 0; i < M; i++) {
for(int j = 0; j < gState; j++) {
for(int k = 0; k < N; k++) {
int next_state;
if(trans[j].child[k])
next_state = trans[j].child[k] - root;
else {
next_state = j;
while(trans[next_state].fault) {
next_state = trans[next_state].fault - root;
if(trans[next_state].child[k]) {
next_state = trans[next_state].child[k] - root;
break;
}
}
}
if(1 != trans[next_state].color)
//dp[i + 1][next_state] += dp[i][j];
dp[1 - flag][next_state] += dp[flag][j];
}
}
for(int t = 0; t < gState; t++)
dp[flag][t] = (BIGINT)0;
flag = 1 - flag;
}
BIGINT sum = (BIGINT)0;
for(int t = 0; t < gState; t++)
sum += dp[flag][t];
cout << sum << endl;
}

int main()
{
input();
solve();
return 0;
}


和AC过的代码运行的数据对比过，代码答案应当是正确的，但是提交时超过了Time Limit，还有很大改进空间。

my sample test data：
Input:
3 3 2
ABC
BC
CA
Output:
16

Input:
2 5 2
AB
AB
ABA
Output:
6

Input:
2 3 2
AB
AB
ABA
Output:
4

Input:
2 3 1
AB
AB
Output:
4

Input:
3 4 2
ABC
CACA
CB
Output:
54

Input:
3 5 2
ABC
BABCA
AB
Output:
144

Input:
4 31 9
ABCD
AAAD
BDDBB
CDCAC
BDA
AA
DBBDBBB
CACDBDBDA
DBBCDDDB
B
Output:
30176034781985

Input:
6 37 7
ABCDEF
BC
DAFBEA
AFEEAE
FF
CDACEEE
EBEBCDE
AE
Output:
2386649102384848081060089069

Input:
4 13 9
ABCD
AD
ACBCDCDDA
DBD
CB
BBDDBADCDC
BDCCDACC
DDDDAC
BCCCBA
ACBCCDDABC
Output:
8189198

Input:
4 12 3
ABCD
BBDDBADCDC
BDCCDACC
DDDDAC
Output:
16747217

Input:
4 5 6
ABCD
AA
BCB
DBA
BDDAD
CCBD
ADBCC
Output:
725

Input:
4 5 3
ABCD
CDBAD
DBC
AC
Output:
733



2 5 4
AB
ABBBB
BBA
AABAA
AA
ref: 5

3 5 3
ABC
ACBBB
CBAB
BC
ref: 139

2 3 2
AB
BB
BB
ref: 5

2 5 3
AB
AA
BBBA
ABBAB
ref: 9

2 5 6
AB
ABABA
BAAB
ABB
AAB
BBBAB
ABBBB
ref: 10

2 5 5
AB
BBA
BABAB
BBAAA
ABBBB
BBAAA
ref: 18

2 6 2
AB
BBA
ABBBBA
ref: 33

2 11 2
AB
BBA
ABBBB
ref: 323