<转自原博客> 可爱的字符串算法们
在非常强又非常关心学弟学妹学习的企鹅学长变态的考纲下，我们无奈中选择一起学习新姿势
first：KMP算法
这是一个小迪更过博客的算法，我就不好意思在这里献丑了，所以献上友链一份：http://rabbithu.xyz/index.php?title=2017-04-01-01
second：Trie树（字典树）
嘤嘤嘤，这就是我在oi小组讲的第一堂课了！？（虽然当天大家都很颓，但是算法的简单是毋庸置疑的！）
在有关字符串的问题中，我们会遇到一些子串啊~前缀啊~的问题，如果正常枚举遍历的话复杂度为O(n*m)（n、m为字串长度），obviously，这很慢！那怎么办呢？
这时候，就有一个十分聪明的人，想到了树！可是树和字符串有啥关系？看图就知道了！
上图这棵树中，边代表字母，结点存储是否是一个单词的结尾，这样我们是不是就可以通过一个26叉树存储任何想要的单词了w！
【如此可知，根节点代表一个空串】
此刻肯定已经有一些人在想怎样代码实现了，链前？显然，如果用链前存储的话，我们无论是插入还是查询都需要在每一层遍历当前字母，这样复杂度岂不是爆炸？所以我们就用一个简单机智的方法实现存儿子的过程！
struct node
{
int data;
int childs[26];
}tree[N];
Trie 的节点可以使用一个结构体进行存储，如下代码中，trans[i]表示这个节点边上字符为i 的转移边所到达的儿子节点编号，若为 0 则表示没有这个儿子。是不是特别喵啊！
插入：若对于一个字符串集合为小写的树中插入一个字符串s 事实上我们只要用O(len)的复杂度，一次存入字母边（检查如果有这条边存在，那么直接下一个，否则建边即可），并且在最后标记是单词的结尾就好了！
void insert()
{
int l=strlen(num),now=1;
for (int i=0;i<l;i++)
{
if (!tree[now].childs[num[i]-'a'])
tree[now].childs[num[i]-'0']=tot++;
now=tree[now].childs[num[i]-'a'];
}
tree[now].end=1;
return ;
}
查询：查询一个字符串 S 是否是给定字符串集合中某个串的前缀： 这有什么好说的？不和插入是一样的吗！如果没有这条边直接return false就好啊【不附代码了，哼唧！】 最后送上一道例题：POJ 3630 //其中用到了插入、查询同时进行的复杂度优化，简单易懂
#include<cstdio>
#include<cstring>
#define M 11
using namespace std;
const int N=1e5+5;
int n,t,tot,ans;
char num[M];
struct hhh
{
bool end;
int childs[M];
void clear()
{
memset(childs,0,sizeof(childs));
end=false;
}
}tree[N]; bool insert()
{
int l=strlen(num),now=1;
for (int i=0;i<l;i++)
{
if (!tree[now].childs[num[i]-'0'])
{
tree[now].childs[num[i]-'0']=tot++;
tree[tot-1].clear();
}
else if (i==l-1) return 0;
now=tree[now].childs[num[i]-'0'];
if (tree[now].end) return 0;
}
tree[now].end=1;
return 1;
} int main()
{
scanf("%d",&t);
while (t--)
{
tot=1;
ans=1;
tree[tot++].clear();
scanf("%d",&n);
while (n--)
{
scanf("%s",num);
if (!insert()) ans=0;
}
if (ans)
printf("YES\n");
else printf("NO\n");
}
return 0;
}
如果有小伙伴看到这里，那你可以去尝试一下poj2001 如果没算错的话，只能用指针来实现Trie树 代码如下：
#include<cstdio>
#include<cstring>
#define N 1111
#define M 22
using namespace std;
int n,i;
char ha[N][M];
struct node
{
int count;
node *childs[26];
node()
{
count=0;
int i;
for(i=0;i<26;i++)
childs[i]=NULL;
}
};
node *root = new node;
node *now,*newnode; void insert(int x)
{
int l=strlen(ha[x]);
now=root;
for (int j=0;j<l;j++)
{
if (now->childs[ha[x][j]-'a'])
{
now=now->childs[ha[x][j]-'a'];
++(now->count);
}
else
{
newnode=new node;
++(newnode->count);
now->childs[ha[x][j]-'a']=newnode;
now=newnode;
}
}
return ;
} void search(int x)
{
now=root;
int l=strlen(ha[x]),cnt=0;
char ans[M];
for (int j=0;j<l;j++)
{
now=now->childs[ha[x][j]-'a'];
ans[cnt++]=ha[x][j];
ans[cnt]='\0';
if (now->count==1)
{
printf("%s %s\n",ha[x],ans);
return ;
}
}
printf("%s %s\n",ha[x],ans);
return ;
} int main()
{
while (~scanf("%s",ha[i])) insert(i++);
for (int j=0;j<i;j++) search(j);
return 0;
}
我觉得不会有人看到这里了…… 以下是20160603模拟easy round1 T2 震惊
Description “震惊，OIer熬夜学习可持久化tire树竟是因为……” ——企鹅头条 钫企鹅听说哦艾尔要加入企鹅头条，书写传奇新闻，夺得普利鹅2333年新闻奖。便让他去震惊部去历练一下。 震惊有一些不同的写法，均由小写字母构成，且长度不超过 100100 。比如 : shock,choc,schock 等。每一种震惊的写法，在震惊部拥有不同的权值。 给定 nn 种震惊写法初始的权值，并进行 mm 个操作。 操作分两种 : 1.修改 : 给出一种震惊的写法，若这种写法存在 , 则将这种震惊写法的权值修改为 xx 。 2.询问 : 在 xx 次操作前，某种震惊写法的权值。即若当前为第 dd 次操作 , 则询问第 d−xd−x 次操作后 , 该种震惊写法的权值 。 注意:本题采用强制在线 , 请注意输入输出格式 Input 第一行两个整数 nn , mm 。 接下来 nn 行每行一个字符串 SS ,和一个整数 xx , 分别代表一种震惊的写法和该种写法的初始权值 。 接下来 mm 行每行一个字符串 SS 和一个整数 xx 。字符串 SS 代表一种震惊的写法。 如果本次操作是修改, xx 代表将这种震惊的写法的权值修改为 xx 。 如果本次操作是询问, xx 代表询问 xx 次操作前，这种震惊写法的权值 。 本题采用强制在线，若上次操作的输出为 Er 或 Shock ,则代表本次操作为询问，否则代表本次操作为修改。规定第 11 次操作为修改 。 Output 输出共 mm 行。每行对应一次操作。 对于每组修改，如果修改成功(即存在对应的震惊写法)，输出 Ac 。如果不存在对应的震惊写法，输出 Er 。 对于每组询问，如果存在对应的震惊写法，输出对应 xx 次操作前，某种震惊写法的权值 xx 。如果不存在对应的震惊写法，输出 Shock 。
题解：暂割
AC代码：
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define M 1111
#define N 11111
#define inf 1111111
using namespace std;
int n,m,x,b,pre,j;
char a[M];
struct ha
{
int time,dt;
bool operator < (ha j) const
{
return time<j.time;
}
ha()
{
time=inf;
dt=0;
}
};
struct hhh
{
vector <ha> data;
bool jy;
hhh *childs[30];
hhh()
{
for(int i=0; i<26; i++)
childs[i]=NULL;
jy=0;
}
};
hhh *root=new hhh;
hhh *now,*newnode; void insert(int y)
{
int l=strlen(a);
now=root;
for (int i=0; i<l; i++)
{
if (now->childs[a[i]-'a'])
now=now->childs[a[i]-'a'];
else
{
newnode=new hhh;
now->childs[a[i]-'a']=newnode;
now=newnode;
}
}
ha u;
u.time=0;
u.dt=y;
now->data.push_back(u);
now->jy=1;
return ;
} void query(int y)
{
now=root;
int l=strlen(a);
for (int i=0; i<l; i++)
{
if (now->childs[a[i]-'a'])
now=now->childs[a[i]-'a'];
else
{
printf("Shock\n");
pre=0;
return ;
}
}
if (!(now->jy))
{
printf("Shock\n");
pre=0;
return ;
}
if (j-y>=0)
{
vector <ha> :: iterator it;
ha uu;
uu.time=j-y;
it=upper_bound(now->data.begin(),now->data.end(),uu);
it--;
printf("%d\n",it -> dt);
}
else
{
int v=now->data.size()-1;
printf("%d\n",now->data[v].dt);
}
pre=1;
return ;
} void change(int y)
{
int l=strlen(a);
now=root;
for (int i=0; i<l; i++)
{
if (now->childs[a[i]-'a'])
{
now=now->childs[a[i]-'a'];
}
else
{
printf("Er\n");
pre=0;
return ;
}
}
if (!(now->jy))
{
printf("Er\n");
pre=0;
return ;
}
printf("Ac\n");
pre=1;
ha u;
u.time=j;
u.dt=y;
now->data.push_back(u);
return ;
} int main()
{
freopen("2(2).in","r",stdin);
freopen("2.out","w",stdout);
scanf("%d%d",&n,&m);
pre=1;
while(n--)
{
scanf("%s %d",a,&b);
insert(b);
}
for (j=1; j<=m; j++)
{
scanf("%s %d",a,&x);
if (pre) change(x);
else query(x);
}
return 0;
}
最新文章
- svn: E200007: Runner for 'org.tmatesoft.svn.core.wc2.SvnMerge' command have not been found; probably not yet implement in this API.
- bzoj1854 游戏
- iOS开发UI篇—Quartz2D简单使用（三）
- TYVJ P1002 谁拿了最多奖学金 Label：模拟 水
- WebForm MapPageRoute 路由配置(转载)
- 使用HttpClient访问被保护资源
- 无线Ad-hoc网络的关键技术之路由(转)
- xcode的ios工程目录结构
- 【Daily】 2014-4-28
- Python 链接MysqlDB
- Web Mining and Big Data 公开课学习笔记 ---lecture1
- 戏说程序猿之cannot find the object
- 观察者模式（Observer）和发布（Publish/订阅模式（Subscribe）的区别
- 引擎设计跟踪(九.14.3) deferred shading 准备
- 使用切片拦截Rest服务
- python项目入门之 安装、创建
- java线程池的应用
- echatrs可视化图在隐藏后显示不出来或是宽度出现问题
- 续写上一篇的数组or指针操作
- Appium+python自动化22-Appium Desktop