這個(gè)題與poj2778dna sequence解法基本一致。只是這個(gè)題的答案沒(méi)有取模，
而且文本串不太長(zhǎng)。問(wèn)題是不取模的話就只能輸出實(shí)際的答案了，就只能用大數(shù)了。
而且用大數(shù)的話，再用矩陣冥可能就會(huì)超時(shí)之類(lèi)的。
這類(lèi)題還可以用除矩陣冥外的另外一種解法，就是直接dp即可。
二維狀態(tài)，第一維代表文本串長(zhǎng)度，第二維代表在AC自動(dòng)機(jī)中的狀態(tài)。
比如dp[i][j]代表長(zhǎng)度為i的文本串，轉(zhuǎn)移到Trie圖中節(jié)點(diǎn)j時(shí)候滿足不包含任何模式串的答案。
剩下的是如何轉(zhuǎn)移狀態(tài)。轉(zhuǎn)移的話也是考慮next指針數(shù)組，設(shè)next = tries[j].next[k]，
那么有dp[i+1][next] = dp[i+1][next] + dp[i][j]，從0到字母集合大小N枚舉k即可。
這個(gè)題有一個(gè)易錯(cuò)的地方，就是字母集合可能是ascii碼在128到256的范圍內(nèi)。而char
的范圍可能是-128到127或者0到255，這個(gè)是根據(jù)編譯器不同的。所以，直接用字符串
數(shù)組讀入數(shù)據(jù)后需要再處理下。可以直接將每個(gè)字符加128后再處理。
另外，getchar返回的是int，但是與gets之類(lèi)的函數(shù)獲得的值的差別也不是那么確定的了。
我覺(jué)得getchar除了對(duì)eof之外其余都返回正值。但是，如果char是有符號(hào)的話，scanf或者
gets之類(lèi)得到的char數(shù)組里面可能就包含負(fù)值了。。。
這個(gè)可以生成隨機(jī)文件，再用getchar讀入并用%d輸出其返回值驗(yàn)證下。驗(yàn)證程序如下：
注釋掉的部分是生成隨機(jī)文件的部分。
#include <stdio.h>
#include <stdlib.h>
int main()
{
char ch;
freopen("in.txt", "r", stdin);
//freopen("in.txt", "w", stdout);
int nNum = 100;
int nCh;
do
{
printf("%d\n", nCh = getchar());
}while (nCh != EOF);
/*while (nNum--)
{
putchar(rand() % 256);
}*/
return 0;
}
該題的代碼如下：
#include <stdio.h>
#include <
string.h>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_D = 256;
const int MAX_N = 51;
const int MAX_M = 51;
const int MAX_P = 11;
struct Trie
{
Trie* fail;
Trie* next[MAX_D];
int no;
bool flag;
};
Trie tries[MAX_P * MAX_P];
int nP;
int nN, nM;
Trie* pRoot;
int nHash[MAX_D];
char szPat[MAX_M];
Trie* NewNode()
{
memset(&tries[nP], 0,
sizeof(Trie));
tries[nP].no = nP;
return &tries[nP++];
}
void InitTrie(Trie*& pRoot)
{
nP = 0;
pRoot = NewNode();
}
void Insert(Trie* pRoot,
char* pszPat)
{
Trie* pNode = pRoot;
while (*pszPat)
{
int idx = nHash[*pszPat];
if (pNode->next[idx] == NULL)
{
pNode->next[idx] = NewNode();
}
pNode = pNode->next[idx];
++pszPat;
}
pNode->flag =
true;
}
void BuildAC(Trie* pRoot)
{
pRoot->fail = NULL;
queue<Trie*> qt;
qt.push(pRoot);
while (!qt.empty())
{
Trie* front = qt.front();
qt.pop();
for (
int i = 0; i < nN; ++i)
{
if (front->next[i])
{
Trie* pNode = front;
while (pNode && pNode->next[i] == NULL)
{
pNode = pNode->fail;
}
front->next[i]->fail = pNode? pNode->next[i] : pRoot;
front->next[i]->flag |= front->next[i]->fail->flag;
qt.push(front->next[i]);
}
else {
front->next[i] = front->fail->next[i];
}
}
}
}
const int MAX_L = 200;
struct BigInt
{
int nD[MAX_L];
BigInt()
{
Clear();
}
void Clear()
{
memset(nD, 0,
sizeof(nD));
}
void Print()
{
int i = MAX_L - 1;
while (!nD[i] && i)--i;
while (i >= 0)
{
putchar(nD[i] + '0');
--i;
}
}
int operator[](
int idx)
const {
return nD[idx];
}
int&
operator[](
int idx)
{
return nD[idx];
}
};
BigInt bi[MAX_M][MAX_D];
BigInt
operator+(
const BigInt& one,
const BigInt& two)
{
BigInt ret;
for (
int i = 0, nAdd = 0; i < MAX_L; ++i)
{
ret[i] = one[i] + two[i] + nAdd;
nAdd = ret[i] / 10;
ret[i] %= 10;
}
return ret;
}
void Solve()
{
BigInt ans;
for (
int i = 0; i <= nM; ++i)
{
for (
int j = 0; j < nP; ++j)
{
bi[i][j].Clear();
}
}
bi[0][0][0] = 1;
for (
int i = 1; i <= nM; ++i)
{
for (
int j = 0; j < nP; ++j)
{
if (tries[j].flag)
continue;
for (
int k = 0; k < nN; ++k)
{
int nNext = tries[j].next[k] - tries;
if (tries[nNext].flag ==
false)
{
bi[i][nNext] = bi[i][nNext] + bi[i - 1][j];
}
}
}
}
for (
int i = 0; i < nP; ++i)
{
ans = ans + bi[nM][i];
}
ans.Print();
printf("\n");
}
int main()
{
int nT;
while (scanf("%d%d%d%*c", &nN, &nM, &nT) == 3)
{
int nCh;
int nTmp = 0;
memset(nHash, 0,
sizeof(nHash));
while (nCh = getchar(), nCh != '\n')
{
if (!nHash[nCh])
{
nHash[nCh] = nTmp++;
}
}
InitTrie(pRoot);
while (nT--)
{
gets(szPat);
Insert(pRoot, szPat);
}
printf("1");
BuildAC(pRoot);
printf("2");
Solve();
}
return 0;
}