关键词：
模板题，字典树最基本的操作
在看别人的板子的时候学到了一点小技巧
下面贴AC代码，顺便补一补字典树相关，顺便放一下橙子讲课的笔记
Trie三兄弟——标准Trie、压缩Trie、后缀Trie
字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽
#include<bits/stdc++.h>
using namespace std;
const int MAX = 5e4 + 5;
string s;
int n, t, ans;
struct Trie {
Trie *next[2];
int vis;
Trie() //这个方法开节点很方便的，码一下
{
for (int i = 0; i<2; i++)
this->next[i] = NULL;
this->vis = 0;
}
};
void insertrie(Trie* rt, string s)
{
int len = s.length();
Trie *p = rt;
for (int i = 0; i<len; i++)
{
int id = s[i] - ‘0‘;
if (p->next[id] == NULL)
{
p->next[id] = new Trie;
}
p = p->next[id];
p->vis++;
ans = max(ans, (i+1)*p->vis);
}
}
int main()
{
cin >> t;
while (t--)
{
cin >> n;
ans = 0;
Trie *rt=new Trie;
for (int i = 0; i<n; i++)
{
cin >> s;
insertrie(rt, s);
}
cout << ans << endl;
}
return 0;
}
小笔记?(^?^*)
背景+定义：字典树进行推广实际上是一个N叉树，字典树相对比较简单，但重要的是在此基础上 的AC自动机比较难。字典树的功能实际上是对于很多的串进行压缩。
板子：
emmmm闭馆了hahahha……明天补
uva11488hyperprefixsets
方法：Trie本题其实就是trie的实现，每个节点需要记录两个值，深度和visit的次数，答案便是max（深度＊visit的次数）。数组实现code:#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<string>#include& 查看详情
uva11488超级前缀集合（trie的应用）
...1串，从中选择一个集合S，使得P(S)最大。 思路：建立字典树，边插入边统计答案即可。用两个变量分别记录前缀数量和前缀长度，每次插入时动态更新两者乘积。1#include< 查看详情
uva3942--remembertheword(字典树+dp)
RemembertheWord Nealisverycuriousaboutcombinatorialproblems,andnowherecomesaproblemaboutwords.KnowingthatRayhasaphotographicmemoryandthismaynottroublehim,NealgivesittoJiejie. SinceJiejiecan’tremembe 查看详情
uva12333大数，字典树
...析：大数模板就是吊哦。将菲波那切数列前500个数字放到字典树上。注意插入的时候不能像普通一样，只在尾节点处标记，而是一路标记下去。#include<bits/stdc++.h>usingnamespacestd;constintNV=10000;constintra=10;intten[4]={1,ra,ra*ra,ra*ra*r 查看详情
uva11520fillthesquare(字典序枚举)
链接：http://vjudge.net/problem/18268分析：从上到下从左到右按字典序从小到大枚举。1#include<cstdio>23constintmaxn=10+5;45intn;6chargrid[maxn][maxn];78intmain(){9intT;10scanf("%d",&T);11for(intkase=1;kase<=T;kase++ 查看详情
字典树（"strcmp()"anyone?uva11732）
strcmp()isalibraryfunctioninC/C++whichcomparestwostrings.Ittakestwostringsasinputparameteranddecideswhichoneislexicographicallylargerorsmaller:Ifthefirststringisgreaterthenitreturnsapositivevalue,ifth 查看详情
uva1584circularsequence(环形串最小字典序)
...形串 输出它以某一位为起点顺时针得到串的最小字典序直接模拟 每次后移一位比較字典序就可以 注意不能用strcpy(s+1,s)这样后移 strcpy复制地址不能有重叠部分#include<cstdio>#include<cstring>usingnamespace... 查看详情
安迪的第一个字典（uva10815)(代码片段)
题目具体描述见：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1756 C++11代码如下：1#include<iostream>2#include<set>3#include&l 查看详情
更新字典（updatingadictionary,uva12504)(代码片段)
题目描述：解题思路：1.根据：和，获得字符串2.使用两个map进行比较；1#include<iostream>2#include<algorithm>3#include<string>4#include<map>5usingnamespacestd;6map<string,string>::iteratorit;7map<strin 查看详情
安迪的第一个字典andy'sfirstdictionary,uva10815
（Timelimit:3seconds）Andy,8,hasadream-hewantstoproducehisveryowndictionary.Thisisnotaneasytaskforhim,asthenumberofwordsthatheknowsis,well,notquiteenough.Insteadofthinkingupallthewordshimself,hehasabril 查看详情
uva1599最佳路径
...org/external/15/1599.pdf 题意：保证在最短路的时候，输出字典序最小的路径。方法：路径上有了权值，可以利用图论的数据结构来BFS，很方便。逆序BFS，找到每个点距离终点的最短路长d[x];然后，从起点，沿着d[u]=d[v]+1;的路径，... 查看详情
uva11404palindromicsubsequence[dplcs打印]
...micSubsequence题意：一个字符串，删去0个或多个字符，输出字典序最小且最长的回文字符串 不要求路径区间DP都可以做然而要字典序最小倒过来求LCS，转移同时维护f[i][j].s为当前状态字典序最小最优解f[n][n].s的前半部分一定是... 查看详情
dnaconsensusstring,(uva,1368)
...是Hamming距离（自行查找），然后注意出现多个解是选择字典序小者（直接将字典序排号比较），**注意数组大小。1#include<stdio.h>2#include<string.h>3#definemaxn10004#definemaxm100056charDNA[maxn 查看详情
uva-1584circularsequence解题报告
....题目大意输入长度为n$(2lenle100)$的环状DNA串，找出该DNA串字典序最小的最小表示。 2.思路 这题特别简单，一一对比不同位置开始的字符串的字典序，更新result。 3.代码#include"stdio.h"#include"string.h"#definemaxn100intjudge(char*s,... 查看详情
uva1584.circularsequence
...blem=4459题目意思：给出一个字符串，求出该字符串的最小字典序 暴力求解即可，用ans保存最小字典序的第一个字符的下标。（好像这方法有点慢，测试的时候，第二个test出 查看详情
安迪的第一个字典（andy'sfirstdictionary,uva10815)(代码片段)
题目描述：#include<iostream>#include<string>#include<set>#include<sstream>usingnamespacestd;set<string>dic;strings,buf;intmain()while(cin>>s)for(inti=0;i<s.length() 查看详情
uva116--unidirectionaltsp(dp)(代码片段)
...bsp;UnidirectionalTSP 题意：求从第一列到最后一列的一个字典序最小的最短路，要求不仅输出最短路长度，还要输出字典序最小的路径。解题思路：设d(i,j)为从格子(i,j)出发，到最后一列的最小开销。因为不仅要输出解，还要输... 查看详情
uva1599idealpath（双向bfs+字典序+非简单图的最短路+队列判重）
...得经过的边数尽量少，在此前提下，经过边的颜色序列的字典序最小。一对结点可能有多条边，一条边可能连接相同的结点（自环）。输入保证结点1可以到达结点n。颜色是1~10^9的 查看详情