一，KMP模式匹配
//模式匹配,kmp算法,复杂度O(m+n)//返回匹配位置,-1表示匹配失败,传入匹配串和模式串和长度#define MAXN 10000int next[MAXN];int pat_match(int ls,char* str,int lp,char* pat){ next[0] = -1; int i=0, j; for (j = 1; j < lp; j++){ //求pat串next数组 for (i = next[j-1]; i >= 0 && !(pat[i+1] == pat[j]); i = next[i]); next[j] = (pat[i+1] == pat[j] ? i+1:-1); } for (i = j = 0; i < ls && j < lp; i++) if (str[i] == pat[j]) j++; else if (j) { j = next[j-1]+1; i--; } return j == lp ? (i-lp):-1;}
二，BM算法
坏字符规则：
当出现一个坏字符时, BM算法向右移动模式串, 让模式串中最靠右的对应字符与坏字符相对，然后继续匹配
如果是未在匹配串出现过得字符，移动nPLen - i;
如果在匹配串出现过，最后的位置是nBadArray，就把匹配串中这个字符与主串对上（但要保证不会使匹配串向左移动需要判断，否则只右移一位），需要移动nPLen - i - 1 - nBadArray;
好后缀规则：
类似KMP算法中的最长前缀，所不同的是，BM算法从字符串的最后开始逐位向前匹配
对于好后缀suffix的一个匹配子串就是从i位置向前数Ni(P)个字符所组成的子串。
而且因为Ni(P)是从i开始向前能够匹配后缀的最长长度，所以可以保证这两个子串之前的一个字符是不相同的。
情况一：
目标串：abcdekxxxxxxx
模式串：cekgek
当从后往前匹配时失配，此时已经匹配上的好后缀为ek，所以我们在模式串的前面部分中查找是否有ek出现，如果有，我们将前面出现的ek挪过来，再继续和目标串进行匹配。本例中模式串1,2位置为ek，移动对上主串的ck。
情况二：
如果匹配上的好后缀部分在前面没有找到，此时我们可以寻找好后缀的后缀中是否有匹配模式串的前缀的情况，如下例：
目标串：abcdekxxxxxxx
模式串：kccgek
虽然ek在模式串的前面没有找到，但是好后缀的一个后缀（k）正好是模式串的一个前缀，所以我们可以将模式串右移。
对于情况一，我们可以先对好后缀数组全部赋值为-1，然后从N-BOX数值的前面往后面遍历一遍，填写对应的好后缀数组。然后我们在来看剩下的好后缀数组中=-1的那些，是否可以用情况二来处理。
对于情况二，找到的是模式串P的前缀，匹配好后缀的后缀，说简单点就是最前面的N个字符匹配最后面的N个字符，我们假设最长的相匹配的前缀、后缀串长度为N（可以在处理情况一的时候顺便得到，具体方法见下面代码），那么对于长度超过N的好后缀，如果它在情况一中没有被填写（也就是不存在完整的匹配），那么根据情况二，好后缀的长度为N的后缀，可以和长度为N的前缀匹配。可以根据这一点来移动模式串。
#include#include #include using namespace std;int nBadArray[256]; //坏字符移动量int nGoodArray[256]; //好后缀移动量int pNBox[101]; //从i处往前数有最长pNBox[i]个字符也是字符串的后缀void BadChar(char *pPattern, int nLen) { for (int i = 0; i < 256; i++) nBadArray[i] = -1; for (int i = 0; i < nLen; i++) nBadArray[(unsigned char) pPattern[i]] = i;}void NBox(const char *pPattern, int nLen, int *pNBox) { pNBox[nLen - 1] = 0; int l = nLen - 1; int r = nLen - 1; for (int i = nLen - 2; i >= 0; i--) { if (i < l) { int n = 0; for (; i >= n && pPattern[i - n] == pPattern[nLen - 1 - n]; n++) ; if (n > 0) { r = i; l = i - n + 1; } pNBox[i] = n; } else { if (pNBox[i + nLen - 1 - r] < i - l + 1) { pNBox[i] = pNBox[i + nLen - 1 - r]; } else { int n = 1; for (int s = l + nLen - 1 - i; l >= n && pPattern[l - n] == pPattern[s - n]; n++) ; pNBox[i] = -(l - n - i); l = l - n + 1; r = i; } } }}void GoodSuffix(char *pPattern, int nLen) { NBox(pPattern, nLen, pNBox); //根据N-BOX确定好后缀的值，首先全部初始化为-1 for (int i = 0; i < nLen; i++) { nGoodArray[i] = -1; //没有好后缀的为-1 } int nMax = 0; for (int i = 0; i < nLen; i++) { nGoodArray[nLen - 1 - pNBox[i]] = i; //好后缀匹配的位置，即通过后缀找到匹配的位置 if (pNBox[i] == i + 1) { //记录下最长的即是前缀也是后缀的位置 nMax = i + 1; } } //补充特殊情况的移动，同一个不完全匹配 if (nMax != 0) for (int i = 0; i < nLen - 1 - nMax; i++) { if (nGoodArray[i] == -1) nGoodArray[i] = nMax - 1; }}int BMSearch(const char* pDest, int nDLen, const char* ppattern, int nPLen) { int nDstart = nPLen - 1; while (nDstart < nDLen) { int i = 0; for (; i <= nPLen - 1 && pDest[nDstart - i] == ppattern[nPLen - 1 - i]; i++) ; if (i > nPLen - 1) { return nDstart - (nPLen - 1); } int nIdxGood = nGoodArray[nPLen - 1 - i]; int nShiftGood = nPLen - 1 - nIdxGood; int nIdxBad = nBadArray[(int) pDest[nDstart - i]]; int nShiftBad = (nIdxBad >= nPLen - 1 - i) ? 1 : nPLen - 1 - i - nIdxBad; nDstart += (nShiftGood > nShiftBad) ? nShiftGood : nShiftBad; } return -1;}int main() { char str[101] = "abcxxxbaaaabaaaxbbaaabcdaaxb"; char pstr[101] = "daaxb"; BadChar(pstr, strlen(pstr)); GoodSuffix(pstr, strlen(pstr)); printf("%d\n", BMSearch(str, strlen(str), pstr, strlen(pstr)));}
三，HASH
为解决冲突，使用链式结构存储，采用3关键字记录，key1用来找到链首，key2和len为特异值用于检验，这里我还加了一个pos来记录这个字符串在原长串中的位置。
typedef unsigned int uint;const int mut1 = 127;const int mut2 = 131;const int MOD = 2000007;struct hash_map { int head[MOD], nEle; struct node { uint key1, key2; int key3, pos, pre; node() { } node(uint key1, uint key2, int key3, int pos, int pre) : key1(key1), key2(key2), key3(key3), pos(pos), pre(pre) { } } ele[MOD * 2]; void init() { nEle = 0; memset(head, -1, sizeof(head)); } int find(uint key1, uint key2, int len) { int hashcode = key1 % MOD; for (int i = head[hashcode]; i != -1; i = ele[i].pre) if (ele[i].key1 == key1 && ele[i].key2 == key2 && ele[i].key3 == len) return i; return -1; } int getPos(uint key1, uint key2, int len) { int pos = find(key1, key2, len); if (pos == -1) return -1; return ele[pos].pos; } void updata(uint key1, uint key2, int len, int pos) { int tmp = key1 % MOD; ele[nEle] = node(key1, key2, len, pos, head[tmp]); head[tmp] = nEle++; } void addstring(string s, int pos) { int len = s.length(); uint key1 = 0, key2 = 0; for (int i = 0; i < len; i++) { key1 = key1 * mut1 + s[i]; key2 = key2 * mut2 + s[i]; } updata(key1, key2, len, pos); }} hash;
四，Trie字典树
//ZOJ 3228 给你一个主串和N个模式串，模式串可以覆盖（0）或者不可以覆盖（1） ，问模式串在主串出现次数#define MAXN 100010#define LETTERS 27int nNodesCount;struct CNode { int index; //指向数组下标位置，方便从next找到的节点找到数组位置 CNode * pChilds[LETTERS]; CNode * pfail; int id[2]; // id[0]为可重叠个数 int pos, len; bool bBadNode; //是否是危险节点 void init() { memset(pChilds, NULL, sizeof(pChilds)); id[0] = id[1] = len = 0; bBadNode = 0; pos = -1; //记录上一次匹配模式串最后字母位置 pfail = NULL; }} Tree[MAXN * 6], *Endpoint[MAXN];void init() { nNodesCount = 1; Tree->init();}void Insert(CNode *pRoot, char *s, int x) { //将模式串s插入 for (int i = 0; s[i]; i++) { if (pRoot->pChilds[s[i] - 'a'] == NULL) { (Tree + nNodesCount)->init(); pRoot->pChilds[s[i] - 'a'] = Tree + nNodesCount; pRoot->pChilds[s[i] - 'a']->index = nNodesCount++; } pRoot = pRoot->pChilds[s[i] - 'a']; } pRoot->bBadNode = 1; pRoot->len = strlen(s); Endpoint[x] = pRoot; // 对应模式串最后一个字符节点储存的信息}void BuildDfa() { //在trie树上加前缀指针 Tree[0].pfail = NULL; deque q; q.push_back(Tree); while (!q.empty()) { CNode * pRoot = q.front(); q.pop_front(); for (int i = 0; i < LETTERS; i++) { CNode * p = pRoot->pChilds[i]; if (p) { if (pRoot == Tree) p->pfail = Tree; else { CNode * pfail = pRoot->pfail; while (pfail) { if (pfail->pChilds[i]) { p->pfail = pfail->pChilds[i]; if (p->pfail->bBadNode) p->bBadNode = 1; //pfail指向的节点是危险节点，则自己后缀包含模式串 break; } else pfail = pfail->pfail; } if (pfail == NULL) //未能找到后缀指针则指向根 p->pfail = Tree; } q.push_back(p); } } } //对应于while(!q.empty())}bool Search(char *s) { CNode * p = Tree; for (int i = 0; s[i]; i++) { while (p != NULL) { if (p->pChilds[s[i] - 'a']) { p = p->pChilds[s[i] - 'a']; if (p->bBadNode) return 1; break; } else p = p->pfail; } } return 0;}void AC_find(char *s) { CNode *p = Tree; for (int i = 0; s[i]; i++) { int k = s[i] - 'a'; while (p->pChilds[k] == NULL && p != Tree) p = p->pfail; p = p->pChilds[k] == NULL ? Tree : p->pChilds[k]; CNode *tmp = p; while (tmp != Tree) { //沿fail指针找到所有包含的模式串 if (tmp->len > 0) { tmp->id[0]++; if (tmp->pos == -1 || i - tmp->pos >= tmp->len) { tmp->id[1]++; tmp->pos = i; // 记录当前单词最后一次出现位置 } } tmp = tmp->pfail; } }}int main() { char str[10], text[MAXN]; int que[MAXN]; int n, d; int cas = 1; while (~scanf("%s", text)) { init(); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%s", &d, str); Insert(Tree, str, i); que[i] = d; } BuildDfa(); AC_find(text); printf("Case %d\n", cas++); for (int i = 0; i < n; i++) printf("%d\n", Endpoint[i]->id[que[i]]); puts(""); } return 0;}
运用Trie字典树与fail指针可以解决很多问题。
1. fail树：fail指针全部反向形成一颗树，这样一个节点的子树的子串都包含节点表示的字符串。
BZOJ 2434 给出一个打字机的操作序列（总长不超过10^5）给出M(1 <= M <= 10^5)个询问(x, y)，查询第x次打印的串在第y次打印的串中出现了几次。
算法分析：想到使用Trie树来存储，并建立成AC自动机，把fail指针全部反向形成的一棵树称为fail树。
考虑询问(x, y)，实质就是在fail树上，找以x的末结点为根的子树上，有多少个结点在AC自动机中root -> y的末结点的路径上。
那么我们再次处理操作序列，就可以很方便地模拟出每一个root -> y末结点路径上的结点都标记为1的情形，对x的询问只需查询一棵子树的和，
经典的苹果树问题，DFS序时间戳 + 树状数组维护。那么，我们把所有与y对应的x答案都处理出来即可。
HDU 4117
给你N个字符串， N(1 <= N <= 2 * 104), 所有串的长度加一起不超过 3 * 105.每个串有个值
从中取若干个字符串，使得前一个串是后一个串的子串，求满足前面调条件的字符串值得和最大，求这个值。
建立AC自动机。后面检查取了以每个字符串是最后取的串的最大值。那么检查第i个字符串的时候，就是这个字符串的未节点前面所有的fail指针一直到根节点和他的上面节点的最大值，加上第i个字符串的值。直接这样暴力的话，是N*M，一定会超时的。
由于每个节点一直fail都会指向根节点，所以把他转化为一棵fail树。我们发现当改变fail树里面的一个节点时，会影响到的是他的子孙，那么就可以用时间戳来把fail树变成线性的从而可以用线段树进行优化。
可是除了fail影响一个节点的还有trie树里面的父节点。所以我们顺着所有的字符扫一遍，存一下上一个走到的结点就是他的trie树中的父节点。和fail树的线段树中比较一下就可以了。
const int kind = 26;const int NN = 333333;int cnt;//ac状态数char str[NN];//所有的字符接在一起int pos[NN];int fail[NN];//每个状态的fail指针int child[NN][kind];//trie树int ans;//最终答案int val[NN];//每个单词输入的valueint tal;//时间戳状态数vector v[NN];//fail树int in[NN];//时间戳int out[NN];int mx[NN<<2];//线段树inline int newNode(){ ++cnt; for(int i=0; i