ST算法可以说就是个二维的动态规划,黑书上有解释。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAX_I = 50010;
const int MAX_J = 20;
int nMax[MAX_I][MAX_J];
int nMin[MAX_I][MAX_J];
int nArr[MAX_I];
int nN, nQ;
void InitRmq(int nN)
{
for (int i = 1; i <= nN; ++i)
{
nMax[i][0] = nMin[i][0] = nArr[i];
}
for (int j = 1; (1 << j) <= nN; ++j)
{
for (int i = 1; i + (1 << j) - 1 <= nN; ++i)
{
nMax[i][j] = max(nMax[i][j - 1],
nMax[i + (1 << (j - 1))][j - 1]);
nMin[i][j] = min(nMin[i][j - 1],
nMin[i + (1 << (j - 1))][j - 1]);
}
}
}
int Query(int nA, int nB)
{
int k = (int)(log(1.0 * nB - nA + 1) / log(2.0));
int nBig = max(nMax[nA][k], nMax[nB - (1 << k) + 1][k]);
int nSml = min(nMin[nA][k], nMin[nB - (1 << k) + 1][k]);
return nBig - nSml;
}
int main()
{
while (scanf("%d%d", &nN, &nQ) == 2)
{
for (int i = 1; i <= nN; ++i)
{
scanf("%d", &nArr[i]);
}
InitRmq(nN);
for (int i = 0; i < nQ; ++i)
{
int nA, nB;
scanf("%d%d", &nA, &nB);
printf("%d\n", Query(nA, nB));
}
}
return 0;
}
该题就是求一个字符串的最长回文子串,就是一个满足本身是回文的最长的子串。
该题貌似可以用后缀数组和扩展kmp做,但是好像后缀数组貌似会tle,改学了下
一个专门的叫Manacher算法的东西。。。
这又是一个线性改良算法。找到有篇文章写的不错,链接如下:
http://www.felix021.com/blog/read.php?2040。
该算法说起来也不是太复杂,比较容易看懂的那种,当然是接触过其它字符串算法
的前提下了。记得以前就看了看,硬是没看懂,想不到现在这么快就明白了。
该算法需要额外的O(N)空间。说起来是空间换时间吧。
大概的思路是先预处理字符串,使其成为一个长度一定为偶数的串。而且第一个字符
是'$',假设'$'没有在原串出现过。然后再在原来的每个字符前面加上'#',最后再加个
'#'。比如,abc就变成了$#a#b#c#。现在再对新的字符串进行处理。
开一个新的数组nRad[MAX],nRad[i]表示新串中第i个位置向左边和向右边同时扩展
并且保持对称的最大距离。如果求出了nRad数组后,有一个结论,nRad[i]-1恰好表示原串
对应的位置能够扩展的回文子串长度。这个的证明,应该比较简单,因为新串基本上是原串
的2倍了,而且新串每一个有效字符两侧都有插入的#,这个找个例子看下就知道是这样了。
最重要的是如何求出nRad数组。
求这个数组的算法也主要是利用了一些间接的结论优化了nRad[i]的初始化值。比如我们求
nRad[i]的时候,如果知道了i以前的nRad值,而且知道了前面有一个位置id,能够最大的向
两边扩展距离max。那么有一个结论,nRad[i] 能够初始化为min(nRad[2*id - i], max - i),
然后再进行递增。关键是如何证明这个,这个的证明,对照图片就很清楚了。
证明如下:
当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和 j 对称,
以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中,所以必有 P[i] = P[j],见下图。
当 P[j] > mx - i 的时候,以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中,但是基于
对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以S[i]为中心的回文子串,其向右至少会
扩张到mx的位置,也就是说 P[i] >= mx - i。至于mx之后的部分是否对称,就只能老老实实去匹配了。
这个就说明得很清楚了。。。
代码如下:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX = 110010 * 2;
char szIn[MAX];
char szOut[MAX];
int nRad[MAX];
int Proc(char* pszIn, char* pszOut)
{
int nLen = 1;
*pszOut++ = '$';
while (*pszIn)
{
*pszOut++ = '#';
nLen++;
*pszOut++ = *pszIn++;
nLen++;
}
*pszOut++ = '#';
*pszOut = '\0';
return nLen + 1;
}
void Manacher(int* pnRad, char* pszStr, int nN)
{
int nId = 0, nMax = 0;
//pnRad[0] = 1;
for (int i = 0; i < nN; ++i)
{
if (nMax > i)
{
pnRad[i] = min(pnRad[2 * nId - i], nMax - i);
}
else pnRad[i] = 1;
while (pszStr[i + pnRad[i]] == pszStr[i - pnRad[i]])
{
++pnRad[i];
}
if (pnRad[i] + i > nMax)
{
nMax = pnRad[i] + i;
nId = i;
}
}
}
int main()
{
while (scanf("%s", szIn) == 1)
{
int nLen = Proc(szIn, szOut);
Manacher(nRad, szOut, nLen);
int nAns = 1;
for (int i = 0; i < nLen; ++i)
{
nAns = max(nRad[i], nAns);
}
printf("%d\n", nAns - 1);
}
return 0;
}
此题就是给出N个字符串,然后求一个最长的子串,它至少出现在N/2+1个字符串中,
如果有多个这样的子串,按字典序输出,如果没有这样的子串,输出?。
此题是罗穗骞论文里面的例11,他有讲述具体的解法。要用后缀数组做这样的题真不
容易,用后缀数组就感觉是一件非常纠结的事情了。
这个题的解法还是那种模式化的思路。把N个字符串连接成一个,注意中间加不出现在
任何一个字符串中的分隔符,然后建立sa数组和height数组等。
最后二分答案,根据答案,即子串的长度对height数组进行分组,分组的思路还是罗穗
骞论文里面例3的思路,即从到后枚举height数组,把连续大于等于答案的值放做一组,
一旦小于答案那么就是新的分组。这个题需要找到一些分组,其中的后缀是能够出现在N个原
串中,这个分组的公共前缀就是sa[i]开始的nMid个字符了(nMid是二分时候获得的子串长度)。
由于这个题需要按字典序输出多个满足要求的子串,所以麻烦了点。需要在Check函数里面
记录这些子串,而且输出答案的时候需要排序,再unique,由于是按height数组的顺序查找的,
而sa[i]已经排好序了,所以排序答案的过程可以省略,但是必须unique。想下Check函数里面
遍历height数组的过程就知道可能出现重复的子串。。。
代码如下:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX_N = 110;
const int MAX_L = 1010;
const int MAX = MAX_N * MAX_L;
int nAns;
char szStr[MAX_L];
char szAns[MAX][MAX_L];
char* pszAns[MAX];
int nNum[MAX];
int nLoc[MAX];
bool bVis[MAX_N];
int sa[MAX], rank[MAX], height[MAX];
int wa[MAX], wb[MAX], wv[MAX], wd[MAX];
bool CmpStr(const char* pszOne, const char* pszTwo)
{
return strcmp(pszOne, pszTwo) < 0;
}
bool EqualStr(const char* pszOne, const char* pszTwo)
{
return strcmp(pszOne, pszTwo) == 0;
}
int cmp(int* r, int a, int b, int l)
{
return r[a] == r[b] && r[a + l] == r[b + l];
}
//倍增算法,r为待匹配数组,n为总长度,m为字符串范围
void da(int* r, int n, int m)
{
int i, j, p, *x = wa, *y = wb;
for (i = 0; i < m; ++i) wd[i] = 0;
for (i = 0; i < n; ++i) wd[x[i] = r[i]]++;
for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wd[x[i]]] = i;
for (j = 1, p = 1; p < n; j *= 2, m = p)
{
for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < n; ++i) wv[i] = x[y[i]];
for (i = 0; i < m; ++i) wd[i] = 0;
for (i = 0; i < n; ++i) wd[wv[i]]++;
for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];
swap(x, y);
for (p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
{
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++;
}
}
}
//求height数组
void calHeight(int* r, int n)
{
int i, j, k = 0;
for (i = 1; i <= n; ++i) rank[sa[i]] = i;
for (i = 0; i < n; height[rank[i++]] = k)
{
if (k) --k;
for(j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
}
}
bool Check(int nMid, int nN, int nK)
{
int nCnt = 0;
int nNo = 0;
memset(bVis, false, sizeof(bVis));
for (int i = 1; i <= nN; ++i)
{
if (height[i] < nMid)
{
nCnt = 0;
memset(bVis, false, sizeof(bVis));
}
else
{
if (!bVis[nLoc[sa[i - 1]]])
{
++nCnt;
bVis[nLoc[sa[i - 1]]] = true;
}
if (!bVis[nLoc[sa[i]]])
{
++nCnt;
bVis[nLoc[sa[i]]] = true;
}
if (nCnt == nK)
{
for (int j = 0; j < nMid; ++j)
{
szAns[nNo][j] = nNum[sa[i] + j];
}
szAns[nNo][nMid] = 0;
++nNo;
nCnt = 0;
}
}
}
if (nNo > 0) nAns = nNo;
return nNo > 0;
}
int main()
{
int nN;
bool bFirst = true;
while (scanf("%d", &nN), nN)
{
if (bFirst) bFirst = false;
else putchar('\n');
int nEnd = 300;
int nP = 0;
for (int i = 0; i < nN; ++i)
{
scanf("%s", szStr);
int nLen = strlen(szStr);
for (int j = 0; j < nLen; ++j)
{
nNum[nP] = szStr[j];
nLoc[nP++] = i;
}
nNum[nP] = nEnd;
nLoc[nP++] = nEnd++;
}
nNum[nP] = 0;
if (nN == 1)
{
printf("%s\n\n", szStr);
continue;
}
da(nNum, nP + 1, 500);//500是估计的字符集大小
calHeight(nNum, nP);
int nLeft = 1, nRight = strlen(szStr);
int nTemp = 0, nMid;
int nK = nN / 2 + 1;
nAns = 0;
while (nLeft <= nRight)
{
nMid = (nLeft + nRight) >> 1;
if (Check(nMid, nP, nK))
{
nTemp = nMid;
nLeft = nMid + 1;
}
else nRight = nMid - 1;
}
if (nTemp == 0)
{
printf("?\n");
}
else
{
for (int i = 0; i < nAns; ++i)
{
pszAns[i] = szAns[i];
}
//sort(pszAns, pszAns + nAns, CmpStr);
nAns = unique(pszAns, pszAns + nAns, EqualStr) - pszAns;
for (int i = 0; i < nAns; ++i)
{
printf("%s\n", pszAns[i]);
}
}
}
return 0;
}
求N个字符串最长的公共子串。这题数据比较水,暴力第一个字符串的子串也可以过。
初学后缀数组,有很多不明白的东西,此题后缀数组的代码在网上也是一把抓。
说实话我确实还不懂后缀数组,但是后缀数组太强大了,只能硬着头皮照着葫芦画瓢了。
贴下代码方便以后查阅吧。。。
感觉后缀数组的应用最主要的还是height数组,看懂倍增算法排序后缀已经非常困难了。
然后再理解height数组怎么用也不是一件容易的事情。然后貌似height数组最关键的用法是
枚举某一个长度的子串时候,比如长度为k,能够用这个k对height数组进行分组,这个罗穗骞
的论文里面有个求不重叠最长重复子串的例子说明了这个height数组分组的思路,不过我现在
还是不怎么理解。。。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX_N = 110;
const int MAX_L = MAX_N * MAX_N;
char szStr[MAX_N];
int nNum[MAX_L];
int nLoc[MAX_L];
bool bVisit[MAX_N];
int sa[MAX_L], rank[MAX_L], height[MAX_L];
int wa[MAX_L], wb[MAX_L], wv[MAX_L], wd[MAX_L];
int cmp(int* r, int a, int b, int l)
{
return r[a] == r[b] && r[a + l] == r[b + l];
}
//倍增算法,r为待匹配数组,n为总长度,m为字符串范围
void da(int* r, int n, int m)
{
int i, j, p, *x = wa, *y = wb;
for (i = 0; i < m; ++i) wd[i] = 0;
for (i = 0; i < n; ++i) wd[x[i] = r[i]]++;
for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wd[x[i]]] = i;
for (j = 1, p = 1; p < n; j *= 2, m = p)
{
for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < n; ++i) wv[i] = x[y[i]];
for (i = 0; i < m; ++i) wd[i] = 0;
for (i = 0; i < n; ++i) wd[wv[i]]++;
for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];
swap(x, y);
for (p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
{
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++;
}
}
}
//求height数组
void calHeight(int* r, int n)
{
int i, j, k = 0;
for (i = 1; i <= n; ++i) rank[sa[i]] = i;
for (i = 0; i < n; height[rank[i++]] = k)
{
if (k) --k;
for(j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
}
}
bool Check(int nMid, int nLen, int nN)
{
int nCnt = 0;
memset(bVisit, false, sizeof(bVisit));
for (int i = 2; i <= nLen; ++i)
{
if (nMid > height[i])
{
nCnt = 0;
memset(bVisit, false, sizeof(bVisit));
continue;
}
if (!bVisit[nLoc[sa[i - 1]]])
{
bVisit[nLoc[sa[i - 1]]] = true;
++nCnt;
}
if (!bVisit[nLoc[sa[i]]])
{
bVisit[nLoc[sa[i]]] = true;
++nCnt;
}
if (nCnt == nN) return true;
}
return false;
}
int main()
{
int nT;
scanf("%d", &nT);
while (nT--)
{
int nN;
int nEnd = 300;
int nP = 0;
scanf("%d", &nN);
for (int i = 1; i <= nN; ++i)
{
scanf("%s", szStr);
char* pszStr;
for (pszStr = szStr; *pszStr; ++pszStr)
{
nLoc[nP] = i;
nNum[nP++] = *pszStr;
}
nLoc[nP] = nEnd;
nNum[nP++] = nEnd++;
reverse(szStr, szStr + strlen(szStr));
for (pszStr = szStr; *pszStr; ++pszStr)
{
nLoc[nP] = i;
nNum[nP++] = *pszStr;
}
nLoc[nP] = nEnd;
nNum[nP++] = nEnd++;
}
nNum[nP] = 0;
da(nNum, nP + 1, nEnd);
calHeight(nNum, nP);
int nLeft = 1, nRight = strlen(szStr), nMid;
int nAns = 0;
while (nLeft <= nRight)
{
nMid = (nLeft + nRight) / 2;
if (Check(nMid, nP, nN))
{
nLeft = nMid + 1;
nAns = nMid;
}
else nRight = nMid - 1;
}
printf("%d\n", nAns);
}
return 0;
}
题意是给定一系列模式串。然后给出一个文本串,问至少改变文本串里面多少个字符
可以使文本串不包含任何一个模式串。
还是先建立Trie图,然后在Trie图上面进行dp。dp的思路也不是很复杂。dp[i][j]的意思
是长度为i的文本串需要改变dp[i][j]个字符顺利到达状态j。需要注意的是长度为i的时候,
对应的字符串中的第i-1个字符。刚开始一直没发现这个bug。而且注意中途不能转移到
匹配成功的状态上去,多加几个条件控制即可了。。。
转移方程,dp[i][j] = min(dp[i][j], dp[i-1][nNext] + szText[i-1] != k),其中nNext
是从状态j可以转移到的非匹配成功的状态,k代表的当前边的权。
代码如下:
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 61;
const int MAX_L = 31;
const int MAX_D = 4;
const int INF = 1110;
char chHash[256];
char szPat[MAX_L];
void InitHash()
{
chHash['A'] = 0;
chHash['G'] = 1;
chHash['C'] = 2;
chHash['T'] = 3;
}
struct Trie
{
Trie* fail;
Trie* next[MAX_D];
bool flag;
int no;
};
int nP;
Trie* pRoot;
Trie tries[MAX_N * MAX_L];
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 = chHash[*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 < 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;
front->next[i]->flag |= front->next[i]->fail->flag;
qt.push(front->next[i]);
}
else
{
front->next[i] = front == pRoot? pRoot : front->fail->next[i];
}
}
}
}
int nChange[INF][INF];
char szText[INF];
int Solve()
{
int nLen = strlen(szText);
for (int i = 0; i <= nLen; ++i)
{
for (int j = 0; j < nP; ++j)
{
nChange[i][j] = INF;
}
}
int i, j, k;
nChange[0][0] = 0;
for (i = 1; i <= nLen; ++i)
{
for (j = 0; j < nP; ++j)
{
if (tries[j].flag) continue;
if (nChange[i - 1][j] == INF) continue;
for (k = 0; k < MAX_D; ++k)
{
int nNext = tries[j].next[k] - tries;
if (tries[nNext].flag) continue;
//trie是边权树,所以i是从1到len,而且当前字符是szText[i-1]
int nTemp = nChange[i - 1][j] + (k != chHash[szText[i - 1]]);
nChange[i][nNext] = min(nChange[i][nNext], nTemp);
}
}
}
int nAns = INF;
for (i = 0; i < nP; ++i)
{
if (!tries[i].flag)
nAns = min(nAns, nChange[nLen][i]);
}
return nAns == INF? -1 : nAns;
}
int main()
{
int nN;
int nCase = 1;
InitHash();
while (scanf("%d", &nN), nN)
{
InitTrie(pRoot);
while (nN--)
{
scanf("%s", szPat);
Insert(pRoot, szPat);
}
BuildAC(pRoot);
scanf("%s", szText);
printf("Case %d: %d\n", nCase++, Solve());
}
return 0;
}
这个题与poj2778dna sequence解法基本一致。只是这个题的答案没有取模,
而且文本串不太长。问题是不取模的话就只能输出实际的答案了,就只能用大数了。
而且用大数的话,再用矩阵冥可能就会超时之类的。
这类题还可以用除矩阵冥外的另外一种解法,就是直接dp即可。
二维状态,第一维代表文本串长度,第二维代表在AC自动机中的状态。
比如dp[i][j]代表长度为i的文本串,转移到Trie图中节点j时候满足不包含任何模式串的答案。
剩下的是如何转移状态。转移的话也是考虑next指针数组,设next = tries[j].next[k],
那么有dp[i+1][next] = dp[i+1][next] + dp[i][j],从0到字母集合大小N枚举k即可。
这个题有一个易错的地方,就是字母集合可能是ascii码在128到256的范围内。而char
的范围可能是-128到127或者0到255,这个是根据编译器不同的。所以,直接用字符串
数组读入数据后需要再处理下。可以直接将每个字符加128后再处理。
另外,getchar返回的是int,但是与gets之类的函数获得的值的差别也不是那么确定的了。
我觉得getchar除了对eof之外其余都返回正值。但是,如果char是有符号的话,scanf或者
gets之类得到的char数组里面可能就包含负值了。。。
这个可以生成随机文件,再用getchar读入并用%d输出其返回值验证下。验证程序如下:
注释掉的部分是生成随机文件的部分。
#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;
}
赤裸裸的字符串最小表示题。所谓字符串最小表示指的是给定一个字符串,假设其可以循环移
位,问循环左移多少位能够得到最小的字符串。
算法即是周源的最小表示法,搜索可以找到相关论文和ppt。
该算法其实也不是太复杂,思路可以这样理解。假设原字符串为s,设s1 = s + s; s2 = s1循
环左移1位;现在处理s1和s2,实际写程序的时候可以通过下标偏移和取模得到s1和s2,而并不需
要生成。
处理过程是这样的,设i和j分别指向s1和s2的开头。我们的目的是找到这样的i和j,假设k是s的
长度,满足条件s1[i,i+k-1] = s2[j,j+k-1] 并且s1[i,i+k-1] 是所有满足条件的字符串中最小的
字符串,如果有多个这样的s1[i,i+k-1] 那么我们希望i最小。
其实这个算法主要是做了一个优化,从而把时间搞成线性的。比如,对于当前的i和j,我们一直
进行匹配,也就是s1[i,i+k] = s2[j,j+k] 一直满足,突然到了一个位置s1[i+k] != s2[j+k]了,
现在我们需要改变i和j了。但是,我们不能只是++i或者++j。而是根据s1[i+k]>s2[j+k]的话i =
i + k + 1,否则j = j + k + 1。这样的瞬移i或者j就能够保证复杂度是线性的了。
问题是如何证明可以这样的瞬移。其实,说穿了也很简单。因为s1[i,i+k - 1] = s2[j,j+k -1]
是满足的,只是到了s1[i+k]和s2[j+k]才出现问题了。假如s1[i+k]>s2[j+k],那么我们改变i为
区间[i+1,i+k]中任何一个值m都不可能得到我们想要的答案,这是因为我们总可以在s2中找到相应
的比s1[m,m+k-1]小的字符串s2[j+m-i,j+m-i+k-1],因为有s1[i+k]>s2[j+k]。
同样对于s1[i+k]<s2[j+k]的情况。
文字可能描述的不是很清楚。看PPT能够根据图进行分析。
代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
int GetMin(string& str)
{
int nSize = str.size();
int i = 0, j = 1, k = 0;
while (i < nSize && j < nSize && k < nSize)
{
char chDif = str[(i + k) % nSize]
- str[(j + k) % nSize];
if (!chDif) ++k;
else
{
if (chDif > 0) i = i + k + 1;
else j = j + k + 1;
if (i == j) ++j;
k = 0;
}
}
return min(i, j);
}
int main()
{
string str;
int nN;
scanf("%d", &nN);
while (nN--)
{
cin >> str;
printf("%d\n", GetMin(str) + 1);
}
return 0;
}
这个题目更奇葩。据说是上一个题的加强版。
题意是给定M个模式串,然后给定长度L,问不超过L的文本至少含有一个模式的情况的总种数。
还是用模式串建立Trie图,根据Trie图建立起路径长度为1的矩阵M。
总情况数目为26^1+26^2+...+26^L。不含模式串的情况总数为矩阵N = M^1+M^2+M^3
+...+M^L的第一行之和。总情况数目减去不含模式串的情况就是答案。
这里用到了矩阵的一些算法,比如快速冥,还有快速冥求和。但是,我用了操作符重载,最悲剧
的是重载后的操作符没有优先级,而我还当作有优先级的在用,所以悲剧了。。。一直样例都过不
去。。。唉,最后才发现了这个问题。。。写了260行左右的代码,前面的一部分代码可以当作矩
阵操作的模板了。。。Trie图的也不错,过几天估计得打印下来用了。。。
代码如下:
#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);
//重载运算符保证不了优先级
if (nN % 2)
{
ans = ans + (
base^nN);
//没优先级啊,必须加括号,查错2个小时了
}
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的判断么?加不加会生成不同的矩阵
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;
}
题意很简单,假定文本集就是A,C,T,G,给定M个模式串,问你长度为N的文本不出现这些模式
串的可能性到底有多少种。。。
确实非常不直观的样子。。。
解法是先学学AC自动机,建立起Trie图,根据trie图可以得到长度为1的路径矩阵,然后再快速
冥得到长度为N的路径矩阵。
说起来都非常纠结,没学过AC自动机更加无法理解。学AC自动机之前据说得先学Trie树和KMP
才好理解。学AC自动机搞Trie图就花费了近2天了,然后弄懂这个题又是一天,好在基本明白了。
马上快比赛了,从长春换到金华也不知道是好是坏。。。还是弱菜啊。。。
贴下我的Trie图+快速冥(直接二分了,没有写成数论里面那种算法)...
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long INT;
const int MOD = 100000;
const int MAX_P = 100;
const int MAX_D = 4;
int nIdx[256];
char szPat[MAX_P];
INT nMatrix[MAX_P][MAX_P];
INT B[MAX_P][MAX_P];
INT A[MAX_P][MAX_P];
void InitIdx()
{
nIdx['A'] = 0;
nIdx['C'] = 1;
nIdx['T'] = 2;
nIdx['G'] = 3;
}
struct Trie
{
Trie* fail;
Trie* next[MAX_D];
int no;
bool flag;
Trie()
{
fail = NULL;
memset(next, 0, sizeof(next));
no = 0;
flag = false;
}
};
Trie tries[MAX_D * MAX_P];
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(char* pszPat)
{
Trie* pNode = pRoot;
while (*pszPat)
{
if (pNode->next[nIdx[*pszPat]] == NULL)
{
pNode->next[nIdx[*pszPat]] = NewNode();
}
pNode = pNode->next[nIdx[*pszPat]];
++pszPat;
}
pNode->flag = true;
}
int BuildAC(Trie* pRoot)
{
memset(nMatrix, 0, sizeof(nMatrix));
pRoot->fail = NULL;
queue<Trie*> qt;
qt.push(pRoot);
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 == true)
{
front->next[i]->flag = true;
}
qt.push(front->next[i]);
}
else
{
front->next[i] = front == pRoot? pRoot : front->fail->next[i];
}
if (front->next[i]->flag == false)
{
nMatrix[front->no][front->next[i]->no]++;
}
}
}
return nP;//节点总个数
}
void MultyMatrix(INT A[][MAX_P], INT B[][MAX_P], INT C[][MAX_P], int nSize)
{
for (int i = 0; i < nSize; ++i)
{
for (int j = 0; j < nSize; ++j)
{
INT nSum = 0;
for (int k = 0; k < nSize; ++k)
{
nSum = (nSum + A[i][k] * B[k][j]) % MOD;
}
C[i][j] = nSum;
}
}
}
void CopyMatrix(INT A[][MAX_P], INT B[][MAX_P], int nSize)
{
for (int i = 0; i < nSize; ++i)
{
for (int j = 0; j < nSize; ++j)
{
A[i][j] = B[i][j];
}
}
}
void MatrixPower(INT M[][MAX_P], int nSize, INT nP)
{
if (nP == 1)
{
CopyMatrix(A, M, nSize);
return;
}
MatrixPower(M, nSize, nP / 2);
MultyMatrix(A, A, B, nSize);
if (nP % 2)
{
MultyMatrix(B, M, A, nSize);
}
else
{
CopyMatrix(A, B, nSize);
}
}
int main()
{
INT nM, nN;
InitIdx();
while (scanf("%I64d%I64d", &nM, &nN) == 2)
{
InitTrie(pRoot);
while (nM--)
{
scanf("%s", szPat);
Insert(szPat);
}
int nSize = BuildAC(pRoot);
MatrixPower(nMatrix, nSize, nN);
INT nAns = 0;
for (int i = 0; i < nSize; ++i)
{
nAns = (nAns + A[0][i]) % MOD;
}
printf("%I64d\n", nAns % MOD);
}
return 0;
}
句子的语法匹配。这个用DFA确实可以很方便做出来,用递归判断之类的应该也可以。
感觉用dfa只需要保证状态转换图对了,基本上就不会出bug了,但是其它的方法去匹配
这种类似正则表达式的字符串就容易出错多了。
百度百科的DFA定义如下:
英文全称:Deterministic Finite Automaton, 简写:DFA
DFA定义:一个确定的有穷自动机(DFA)M是一个五元组:M=(K,Σ,f,S,Z)其中
① K是一个有穷集,它的每个元素称为一个状态;
② Σ是一个有穷字母表,它的每个元素称为一个输入符号,所以也称Σ为输入符号字母表;
③ f是转换函数,是K×Σ→K上的映射,即,如 f(ki,a)=kj,(ki∈K,kj∈K)就意味着,
当前状态为ki,输入符为a时,将转换为下一个状态kj,我们把kj称作ki的一个后继状态;
④ S ∈ K是唯一的一个初态;
⑤ Z⊂K是一个终态集,终态也称可接受状态或结束状态。
该题的状态转换图:
现在再根据状态转换图,写一个模拟转换关系的匹配就非常方便了。。。
代码如下:
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
string strNouns[8] =
{
"tom", "jerry", "goofy", "mickey",
"jimmy", "dog", "cat", "mouse"
};
bool IsNoun(string& str)
{
for (int i = 0; i < 8; ++i)
{
if (str == strNouns[i])
{
return true;
}
}
return false;
}
bool IsVerb(string& str)
{
return str == "hate" || str == "love"
|| str == "know" || str == "like"
|| str == "hates" || str == "loves"
|| str == "knows" || str == "likes";
}
bool IsArticle(string& str)
{
return str == "a" || str == "the";
}
bool CheckState(vector<string>& vs)
{
if (vs.empty()) return false;
int nState = 0;
for (int i = 0; i < vs.size(); ++i)
{
//printf("nState:%d, str:%s\n", nState, vs[i].c_str());
switch (nState)
{
case 0:
if (IsArticle(vs[i]))
{
nState = 1;
break;
}
else if (IsNoun(vs[i]))
{
nState = 2;
break;
}
else
{
return false;
}
case 1:
if (IsNoun(vs[i]))
{
nState = 2;
break;
}
else
{
return false;
}
case 2:
if (vs[i] == "and")
{
nState = 0;
break;
}
else if (IsVerb(vs[i]))
{
nState = 3;
break;
}
else
{
return false;
}
case 3:
if (IsArticle(vs[i]))
{
nState = 4;
break;
}
else if (IsNoun(vs[i]))
{
nState = 5;
break;
}
else
{
return false;
}
case 4:
if (IsNoun(vs[i]))
{
nState = 5;
break;
}
else
{
return false;
}
case 5:
if (vs[i] == "and")
{
nState = 3;
break;
}
else if (vs[i] == ",")
{
nState = 0;
break;
}
else
{
return false;
}
}
}
return nState == 5;
}
int main()
{
int nT;
scanf("%d%*c", &nT);
while (nT--)
{
vector<string> vs;
string line, str;
getline(cin, line);
stringstream ss(line);
while (ss >> str)
{
vs.push_back(str);
}
printf("%s\n", CheckState(vs) ? "YES I WILL" : "NO I WON'T");
}
return 0;
}