這個(gè)題目更奇葩。據(jù)說是上一個(gè)題的加強(qiáng)版。
題意是給定M個(gè)模式串，然后給定長(zhǎng)度L，問不超過L的文本至少含有一個(gè)模式的情況的總種數(shù)。
還是用模式串建立Trie圖，根據(jù)Trie圖建立起路徑長(zhǎng)度為1的矩陣M。
總情況數(shù)目為26^1+26^2+...+26^L。不含模式串的情況總數(shù)為矩陣N = M^1+M^2+M^3
+...+M^L的第一行之和。總情況數(shù)目減去不含模式串的情況就是答案。
這里用到了矩陣的一些算法，比如快速冥，還有快速冥求和。但是，我用了操作符重載，最悲劇
的是重載后的操作符沒有優(yōu)先級(jí)，而我還當(dāng)作有優(yōu)先級(jí)的在用，所以悲劇了。。。一直樣例都過不
去。。。唉，最后才發(fā)現(xiàn)了這個(gè)問題。。。寫了260行左右的代碼，前面的一部分代碼可以當(dāng)作矩
陣操作的模板了。。。Trie圖的也不錯(cuò)，過幾天估計(jì)得打印下來用了。。。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned
long long INT;
const int MAX_D = 26;
const int MAX_L = 10;
const int MAX_N = 10;
char szPat[MAX_L];
const int MAX_S = 31;
struct Matrix
{
int nSize;
INT nD[MAX_S][MAX_S];
Matrix(
int nS)
{
Clear(nS);
}
Matrix&
operator = (
const Matrix& m)
{
nSize = m.nSize;
for (
int i = 0; i < nSize; ++i)
{
for (
int j = 0; j < nSize; ++j)
{
nD[i][j] = m.nD[i][j];
}
}
return *
this;
}
void Clear(
int nS)
{
nSize = nS;
memset(nD, 0,
sizeof(nD));
}
void Unit()
{
for (
int i = 0; i < nSize; ++i)
{
for (
int j = 0; j < nSize; ++j)
{
nD[i][j] = (i == j ? 1 : 0);
}
}
}
};
Matrix
operator+(
const Matrix& A,
const Matrix& B)
{
Matrix C(A.nSize);
for (
int i = 0; i < A.nSize; ++i)
{
for (
int j = 0; j < A.nSize; ++j)
{
C.nD[i][j] = A.nD[i][j] + B.nD[i][j];
}
}
return C;
}
Matrix
operator*(
const Matrix& nA,
const Matrix& nB)
{
Matrix nC(nB.nSize);
for (
int i = 0; i < nA.nSize; ++i)
{
for (
int j = 0; j < nA.nSize; ++j)
{
for (
int k = 0; k < nA.nSize; ++k)
{
nC.nD[i][j] += nA.nD[i][k] * nB.nD[k][j];
}
}
}
return nC;
}
Matrix
operator^(Matrix B, INT nExp)
{
Matrix ans(B.nSize);
ans.Unit();
while (nExp)
{
if (nExp % 2)
{
ans = ans * B;
}
B = B * B;
nExp >>= 1;
}
return ans;
}
//求base^1+base^2+
+base^N
Matrix SumPowMatrix(Matrix&
base, INT nN)
{
if (nN == 1)
{
return base;
}
Matrix ans = SumPowMatrix(
base, nN / 2);
ans = ans + ((
base^(nN / 2)) * ans);
//重載運(yùn)算符保證不了優(yōu)先級(jí)
if (nN % 2)
{
ans = ans + (
base^nN);
//沒優(yōu)先級(jí)啊,必須加括號(hào),查錯(cuò)2個(gè)小時(shí)了
}
return ans;
}
struct Trie
{
Trie* next[MAX_D];
Trie* fail;
int no;
bool flag;
};
Trie tries[MAX_L * MAX_N];
int nP;
Trie* pRoot;
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 = *pszPat - 'a';
if (pNode->next[idx] == NULL)
{
pNode->next[idx] = NewNode();
}
pNode = pNode->next[idx];
++pszPat;
}
pNode->flag =
true;
}
void BuildAC(Trie* pRoot, Matrix& M)
{
pRoot->fail = NULL;
queue<Trie*> qt;
qt.push(pRoot);
M.Clear(nP);
while (!qt.empty())
{
Trie* front = qt.front();
qt.pop();
for (
int i = 0; i < MAX_D; ++i)
{
if (front->next[i])
{
Trie* pNode = front->fail;
while (pNode && pNode->next[i] == NULL)
{
pNode = pNode->fail;
}
front->next[i]->fail = pNode? pNode->next[i] : pRoot;
if (front->next[i]->fail->flag)
{
front->next[i]->flag =
true;
}
qt.push(front->next[i]);
}
else {
front->next[i] = front == pRoot? pRoot : front->fail->next[i];
}
//這里必須要加上front->flag為false的判斷么?加不加會(huì)生成不同的矩陣
if (!front->next[i]->flag)
{
++M.nD[front->no][front->next[i]->no];
}
}
}
}
int main()
{
int nN;
INT nL;
Matrix M(0);
while (scanf("%d%I64u", &nN, &nL) == 2)
{
InitTrie(pRoot);
while (nN--)
{
scanf("%s", szPat);
Insert(pRoot, szPat);
}
BuildAC(pRoot, M);
Matrix tmp(1);
tmp.nD[0][0] = 26;
tmp = SumPowMatrix(tmp, nL);
INT nAns = tmp.nD[0][0];
Matrix msum = SumPowMatrix(M, nL);
for (
int i = 0; i < msum.nSize; ++i)
{
nAns -= msum.nD[0][i];
}
printf("%I64u\n", nAns);
}
return 0;
}