|
一、Trie树
1.定义： 通过字符串建成一棵树，这棵树的节点个数一定是最少的。例如：4个字符串'ab','abc','bd','dda'对应的trie树如下： 其中红色节点表示存在一个字符串是以这个点结尾的。 一个性质：在树上，两个点u,v满足u是v的祖先，那么u代表的字符串一定是v代表的字符串的前缀。
2.Trie树的插入： 可以从根节点出发，每次沿着要走的字符串往下走，若没有则建立新节点。 假如所有字符串的长度之和为n，构建这棵trie树的时间复杂度为O(n)。 int root=1; int cnt=1; int p[i][j];//表示从i这个节点沿着j这个字符走，能走到哪个点，走不到就是0 char s[];//存储字符串 for(int i=1;i<> { scanf('%s',s); int len=strlen(s); int now=root;//now表示走到的当前节点，now的初始值为根节点 for(intj=0;j<> { if(p[now][s[j]]>0){ now=p[now][s[j]];//如果能沿着j节点往下走，直接往下走 } else{ pow[now][s[j]]=++cnt; now=p[now][s[j]]; } } v[now]++;//记录now这个节点被访问的次数 }
3.Trie树的查询： 可以看出trie树中每个节点表示其中一个字符串的前缀，在做题过程中往往通过这个性质来得到较好的时间复杂度。
4.一个例题： 给定n个互不相同的串，求存在多少对数(i,j)（共n2对）满足第i个串是第j个串的前缀。 所有串的长度之和≤500000。 解题：根据性质，“在树上，两个点u,v满足u是v的祖先，那么u代表的字符串一定是v代表的字符串的前缀”。 我们要满足一个串是另一个串的前缀，也就是说，在trie树上，这个串对应的位置是另一个串对应的位置的祖先。 构建这棵trie树，然后我们枚举每个红色点，它对答案的贡献是以它为根的子树中红色节点的个数之和。这个东西可以在一开始遍历这棵树预处理出来！ 时间复杂度是线性的。
void dfs(int x) { if(v[x]) sum[x]++; for(chari='a';i<> { if(p[x][i])//从当前x沿着i这个字符走还能往下走 { dfs(p[x][i]);//往下走 sum[x]+=sum[p[x][i]];//累加贡献sum } } } dfs(1);//从根节点开始 5.USACO的某题： 给定n个串，重排字符之间的大小关系，问哪些串有可能成为字典序最小的串。 所有字符串的长度之和<>。 例如，有一个字符串，里面只有'a'~'z'这些字符，默认地，'a'是最小的，'z'是最大的。但是我们可以重新定义字符间的大小关系，比如这样：b<><><><><>，从而我们对于一些字符串，就按照我们新定义的大小关系来比较字典序大小。 举个栗子： 三个字符串'aab','aba','baa'，总共只出现了两个字符'a'和'b'，所以字符间的大小关系要么是a<>要么是a>b，假设a<>，则第一个串'aab'就是字典序最小的串；假设b<>，则第三个串'baa'就是字典序最小的串，但是对于第二个串，无论我们怎么定义字符间的大小关系，都不可能成为三个字符串中字典序最小的。 解题：首先对这n个串构建trie树，之后对每个串，从根走向它，这个路程中遇到的所有兄弟在字典序下都比它大。 对于每个串，从前往后，直接确定这个字符的大小关系，判断是否是字典序最小。 以下两个串都是有可能成为字典序最小的串的： abcd…xyza abcd…xyzb 所以有：u是v的前缀，则v一定不是字典序最小的串。 现在问题来了：对于每个串，在什么条件下，是字典序最小的？？ 来个栗子：有一些字符串（'aabc'，'aac'，'aad'，'ac'，'adb'，'aabb'），构造trie树如下：
对于'aabc'这个串，往下遍历： 从深度为2的那一层，我们可以得到：a<><>； 从深度为3的那一层，我们可以得到：b<><>； 从深度为4的那一层，我们还可以得到：c<>。 综上所述：我们得到了一堆的关系：a<><>；b<><>；c<>，容易看出，这些关系是存在矛盾的，所以无解->'aabc'是不可能成为字典序最小的串。 所以要想有解，这一堆的关系必须满足两个条件：①不存在矛盾②不存在环 总的来说，就是判断这一堆的关系是否存在拓扑序！ 最多有26×26个大小关系，而最多有100000个字符串，所以时间复杂度最大为：O(26×26×100000)。
二、KMP算法
给定两个字符串A,B，判断T是否为S的子串（变式：寻找子串B在串A中的位置）。 要求一个O(|A|+|B|)的做法。 通常称A为目标串（或主串），B为模式串。 算法过程： 我们假设串A的长度为n，串B的长度为m，每个字符串的开头下标默认为1。
定义两个变量i和j，这两个变量共同表示：A[i-j+1~i]与B[1~j]均匹配，即：A中以第i个字符结尾的、长度为j的字符串，和B从头开始长度为j的字符串完全匹配。
继续往下匹配：如果i+1和j+1不匹配。
现在，就是用到了KMP算法的核心：它对这一情况的处理方式是减少j，就相当于将子串向右平移。 平移的目的是为了让“A[i-j+1~i]与B[1~j]均匹配”这个条件重新满足。 在上图中，j一直减小到了0，因为向右平移的过程中，始终不能让这个条件满足（最右边'?'部分已经越界） 但有时候，将j减少一点点之后，是可以重新满足条件的，例如：
那么我们将j从7减小到4时，有：
这样就可以完全匹配啦！但是后面还有没有匹配的机会我们就不管了，至少我们已经保证A[4~7]和B[1~4]完全匹配上了。 现在考虑一个问题：我们每次把j减小1（一位一位地平移B字符串），这样太慢了，我们在这里预处理一个next[]数组，表示当j匹配不下去的时候，我们可以把j减少到next[j]，继续尝试匹配。 预处理过程：让j自己和自己匹配一下，一旦匹配发现B[k-m+1~k] 和 B[1~m] 匹配，则说明在A与B匹配过程中，j等于k匹配不下去时，j可以尝试减小到m。 过程如下：
/**************************************///靓丽的分界线
一些代码：
/*核心内容*/ for(int i=1,j=0;i<> { while(j&&B[j+1]!= A[i]) j=next[j]; if(B[j+1]==A[i]) j++; if(j==m) { printf('%d\n', i-j+1);//输出找到的'B字串在 A中位置' //如果要求的是出现次数，这里也有可能是ans++什么的 j=next[j];//让循环进行下去 } }
for(int i=2,j=0;i<=m;i++)>预处理next[]数组*/ { while(j&&B[j+1]!=B[i]) j=next[j]; if(B[j+1]==B[i]) j++; next[i]=j; }
经典例题：Blue jeans（POJ 3080） 给定m个串，求字典序最小的公共子串。找一个串，使得这个串是所有串的子串，并且字典序最小。 m≤10，每个串的长度≤60. 解题思路：一个串，如果是所有串的子串，那么肯定是第一个串的子串。 枚举所有子串，复杂度为60*60。 验证其它串是否包含这个子串，复杂度为10*60。 每次更新答案即可。 时间复杂度为：O(603×10) 经典例题：Seek the Name,Seek the Fame（POJ 2752） 给定一个字符串S，求所有既是S的前缀又是S的后缀的子串，从小到大输出这些串的长度。 |S|<>。 N为字符串S的长度。
解题思路： 回到KMP算法，我们令P[j]表示找最大的数x，使得B中位置是1~x的字符与j-x+1~j的字符完全相同，也就是上面讲的KMP算法中的next[]。 考虑P[|S|]的意义，也就是最大的前缀等于后缀的长度（不包括其本身）。 那P[P[|S|]]就是次大的。 因此所有P[P[…P[|S|]]]就是答案了，一直这样递归下去就可以找到答案。 或者用Hash来做，这样更容易想到也比较方便，但效率没有KMP高。
三、AC自动机
有n个模式串，长度之和是|T|，有一个主串，长度是|S|，问哪些模式串是这个主串的子串（或者有多少个模式串在主串中出现过）？ 解法一：直接跑n次KMP算法，时间复杂度：O(n×|S|)。 解法二：AC自动机，时间复杂度：O(|T|+|S|)，对于n个串，构建trie树，在trie树上做KMP。 在这里我来详解一下AC自动机啊~ 首先我们定义一个指针，叫做“失配指针”或者“失败指针”，在KMP算法中，这个失配指针就是next[]数组，同样地在AC自动机中，在trie树上也定义一个失配指针与此类似但不完全相同。 失配指针：假设一个节点k的失配指针指向j，那么k、j满足性质：设根节点root到j的距离为n，则从k以上的第n个节点到k这个节点所组成的长度为n的单词，与根节点root到j所组成的单词完全相同。 如下图：
单词'she'中的'e'的失配指针指向的是单词'her'中的'e'，因为红框中的部分是完全一样的。 然后，问题来了，我们该怎样处理这个失配指针呢？其实我们可以用BFS就很方便地解决了。 处理过程：让和根节点直接相连的节点的失配指针指向根节点，对于其他节点（假设为a），设这个节点上的字母为ch，沿着a的父亲b的失配指针走，一直走到一个节点c，c的儿子中也有字母为ch的节点d，然后把a节点的失配指针指向c节点的儿子d（因为d的字母也为ch），如果一直走到了根节点都没找到，那就把失配指针指向根节点。 最开始，我们把根节点加入队列(根节点的失败指针显然指向自己)，这以后我们每处理一个点，就把它的所有儿子加入队列，直到搞完。 这样我们就得到了一棵带有失配指针的trie树了，接下来正式介绍AC自动机工作原理！ AC自动机原理：对于一棵trie树，我们用黄色表示一个单词（某个模式串）的末尾，也就是说从根节点走到一个黄色的点，就组成一个“单词”，如下图：
一开始，trie树中有一个指针t1指向根节点root，将这n个模式串合并为一个模式主串，模式主串中有一个指针t2指向这个模式主串的串头。 接下来进行类似KMP算法的操作：如果t2指向的字母，是trie树中，t1指向的节点的儿子，那么把t2+1，t1改为那个儿子的编号，否则t1顺这当前节点的失配指针往上找，直到t2是t1的一个儿子，或者t1指向根为止。 如果t1经过了一个黄色的点，那么以这个点结尾的单词就算出现过了（这个模式串已经在主串中出现了），或者如果t1所在的点可以沿着失配指针走到一个黄色的点，那么以那个黄色的点为结尾的单词就算出现过了（这个模式串已经在主串中出现了），记录答案即可。
经典例题：假装是字符串的题——正则表达式 给定一个字符串，判断其是否为合法的正则表达式。 一个正则表达式定义为： ①0是正则表达式，1也是正则表达式。 ②P和Q都是正则表达式，则PQ也是正则表达式。 ③P是正则表达式，则(P)是正则表达式 ④P是正则表达式，则P*也是正则表达式 ⑤P和Q都是正则表达式，则P|Q是正则表达式 举个栗子： 010101101* (11|0*)* 以上都是都是正则表达式 |S|<> 解题思路：令dp[i][j]表示第i个字符到第j个字符能否组成正则表达式，分5种情况进行转移就可以了。
四、随机算法
①随机生成一棵树：
for(int i=2;i<=n;i++)>随机生成一棵树*/ { cout<><'><><> }//深度为lgn
②随机生成一棵长毛的链：
/*随机生成一棵长毛的链：1~n/2*/ for(int i=2;i<=n ;i++)=""><><><> for(int i=n/2+1;i<=n;i++)><><><>
③给你一张图，生成一张图：
/*给你一张图，生成一张图，10万个点，20万条边 */ map for(int i=1;i<> { int A=rand()%n+1; int B=rand()%n+1; while(A==B||mp[1ll*A*100005+B]) { A=rand()%n+1; B=rand()%n+1; } mp[1ll*A*10005+B]=1; cout<><><><> }
④随机生成一个连通图： 先生成一棵树，这棵树上的边是一定存在的，在随机其他的边。 另：为感谢各位家长一直以来对融科信息学的信任与支持，在双十二来临之际，特推出双十二底价团购信息学课程，详情点击链接→融科教育双十二同学“惠”，信息学课程底价疯狂抢！（←点击链接，了解活动详情吧） 长沙信息学竞赛 |
|
|
