题解 P2580 【于是他错误的点名开始了】
声明:
此题解非正常Trie,推荐先学习最普通的Trie并了解指针的使用
废话:
很早之前就想到了一种字典树,节点存储字符串,代表Trie树上以某字符开头的所有子树最长公共前缀.好像说的不清楚,那就再听我仔细讲解吧
写题解的上午有了灵感,然后根据思路模拟了一下,可行性挺高的.
写完代码后提交AC,跑了最优解第四,然而前三用的hash算法没法比啊.
我现暂且命名它为Ciyang_Trie(Lumpy_Trie块状字典树),怀疑已经有人发明过了.
代码比普通的复杂一些,我使用了指针.
按任意顺序插入abcd,abcde,bcde,bcef四个字符串的Trie树长这样:
红色节点代表有插入的字符串结尾的节点.
证明:
通过与比较普通指针版和非指针版Trie来证明一下可行性.
指针版Trie可使用动态内存,缺点是每个节点只保存一个字符,而同时又要保存26个子节点的指针,会有大量的空指针来占用额外的内存,且new节点多了,内存分配常数较大.
为了减少常数,可以自己写new方法来分配,但无论是什么数据,只要稍带随机性,就会有很多只有一个子节点的节点,这无疑有25个空指针浪费内存.
非指针版常数小,但空间分配也是很大的问题.
然而仍有很多一条链的树,空间最大浪费N*25啊...先不说影响美观而且时间复杂度依然很高,毕竟查询也是O(N).
Lumpy_Trie的复杂度是会改变的,就是对一条链情况的优化,理论最大时间复杂度是O(N)带有一些常数.
Lumpy_Trie缺点是写起来比普通的更复杂,优点是经得起大数据考量,而且插入最小是O(1),空间上也少了很多空指针.
Lumpy_Trie巧妙利用字符串指针,赋值、继承等操作只需要指针或长度变化就好了.
太多证明不如一句代码,我放上代码继续分析.
解析:
节点的结构体,相比普通Trie多了length和字符串指针:
#define clear(a) memset(a, 0, sizeof(a))
#define copy(a, b) memcpy(a, b, sizeof(a))
struct Lumpy_Tnode {
const char *pStr;
//指向当前存储字符串首元素
int length, isEnd;
//length存储字符串的长度 isEnd代表是否是结尾节点
Lumpy_Tnode *children[26];
//26个子节点
inline Lumpy_Tnode() {
pStr= 0, length= isEnd= 0, clear(children);
}
inline Lumpy_Tnode(const char *str, int len, int end) {
pStr= str, length= len, isEnd= end, clear(children);
}
//构造函数
} mNode;插入操作:
使用递归和循环,判断比较多,先看代码(看起来常数很大)
inline void insert(const char *str, int length, Lumpy_Tnode *bNode) {
//str是指针,指向当前插入字符串的第一个元素
if(!length) {
//字符串长度为0代表结尾
//其实是为了优化代码美观,当作递归边界
bNode->isEnd= 1;
return;
}
int ch= str[0] - 'a';
if(bNode->children[ch]) {
//子节点已存在
bNode= bNode->children[ch];
register int sptr= 0;
while(sptr < length && sptr < bNode->length && bNode->pStr[sptr] == str[sptr]) ++sptr;
//循环来找当前字符串和节点存储的字符串最长前缀
if(sptr != bNode->length) {
//节点存储的字符串不是插入字符串的子串
Lumpy_Tnode *nNode= new Lumpy_Tnode(bNode->pStr + sptr, bNode->length - sptr, bNode->isEnd);
//拆树,运用字符串指针连续地址的特性来操作
copy(nNode->children, bNode->children), clear(bNode->children);
//继承原有子节点的各种信息
bNode->isEnd= 0, bNode->children[bNode->pStr[sptr] - 'a']= nNode;
//清空原有节点,重新初始化
}
bNode->length= sptr;
//更新当前节点存储的字符串长度,从而更改当前存储的字符串
insert(str + sptr, length - sptr, bNode);
}
else
bNode->children[ch]= new Lumpy_Tnode(str, length, 1);
//不存在当前首字母的子节点,直接new并且赋值
//因为是指针操作,所以不需要O(n)复制字符串,理论上复杂度O(3)?
return;
}
//调用方式:insert(插入字符串, 字符串长度, Trie根节点);如果代码看懂了,第一反应可能认为指针操作有问题.
的确插入的字符串在插入后就不能进行改变了,所以就只要开一个char[N][K]的数组来保存输入的字符串,K为最长字符串的长度.
相比较空间复杂度总体仍然较小,其实是把原来每个节点存的char放到了一起,每个节点多了一个指针.(不过创建的节点更少了,所以浪费空间少)
这其中其实有个很巧妙的事,树上的一条链可能指向的地址是连续的.仔细想了想,其实也有空间浪费,不管是节点上还是树上的最长公共前缀都只指向一个字符串,其他字符串中相同的字符占用的空间就永远浪费掉了,这句话不懂没事,因为这个浪费造成的影响很小.
如果代码都没看懂,还有图解:
- 向空树插入abc,再插入ab:
- 再向此树插入ac:
解释一下图2:
比较ab和ac,最长公共前缀为a
新建一个字符串指针指向ab中b的节点,长度为1,继承ab的颜色和ab的子节点.
清空ab的子节点,颜色改为黑(黑表示不为结尾节点),ab的首字母b子节点指向b.
在我实现时,先更改长度使ab变为a,再向a中插入c.
因为没有首字母为c的子节点,直接new一个新的.
查找操作:
inline int find(const char *str, int length, Lumpy_Tnode *bNode) {
if(!length) {
//递归到查找的字符串长度为0
//判断当前节点是否为结尾,是否是第一次查询
if(bNode->isEnd == 1) return bNode->isEnd++;
return bNode->isEnd;
}
int ch= str[0] - 'a';
if(bNode->children[ch]) {
bNode= bNode->children[ch];
if(length < bNode->length) return 0;
//自带剪枝,若当前查找字符串长度小于当前公共前缀,那么字典树中不存在当前查找的字符串
register int sptr= 0;
while(sptr < bNode->length && bNode->pStr[sptr] == str[sptr]) ++sptr;
if(sptr != bNode->length) return 0;
//最长公共前缀必须是当前查找的字符串的子串
return find(str + sptr, length - sptr, bNode);
}
return 0;
//没有子节点,字典树中不存在当前查找的字符串
}
//调用方式:find(查询字符串, 字符串长度, Trie根节点);比插入的代码简单多了,并且自带剪枝,所以比较快.
完整代码:
(开启O2)用时: 127ms / 内存: 4248KB
(关闭O2)用时: 144ms / 内存: 4128KB
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define clear(a) memset(a, 0, sizeof(a))
#define copy(a, b) memcpy(a, b, sizeof(a))
struct Lumpy_Trie {
struct Lumpy_Tnode {
const char *pStr;
int length, isEnd;
Lumpy_Tnode *children[26];
inline Lumpy_Tnode() {
pStr= 0, length= isEnd= 0, clear(children);
}
inline Lumpy_Tnode(const char *str, int len, int end) {
pStr= str, length= len, isEnd= end, clear(children);
}
} mNode;
inline void insert(const char *str, int length, Lumpy_Tnode *bNode) {
if(!length) {
bNode->isEnd= 1;
return;
}
int ch= str[0] - 'a';
if(bNode->children[ch]) {
bNode= bNode->children[ch];
register int sptr= 0;
while(sptr < length && sptr < bNode->length && bNode->pStr[sptr] == str[sptr]) ++sptr;
if(sptr != bNode->length) {
Lumpy_Tnode *nNode= new Lumpy_Tnode(bNode->pStr + sptr, bNode->length - sptr, bNode->isEnd);
copy(nNode->children, bNode->children), clear(bNode->children);
bNode->isEnd= 0, bNode->children[bNode->pStr[sptr] - 'a']= nNode;
}
bNode->length= sptr;
insert(str + sptr, length - sptr, bNode);
}
else
bNode->children[ch]= new Lumpy_Tnode(str, length, 1);
return;
}
inline int find(const char *str, int length, Lumpy_Tnode *bNode) {
if(length == 0) {
if(bNode->isEnd == 1) return bNode->isEnd++;
return bNode->isEnd;
}
int ch= str[0] - 'a';
if(bNode->children[ch]) {
bNode= bNode->children[ch];
if(length < bNode->length) return 0;
register int sptr= 0;
while(sptr < bNode->length && bNode->pStr[sptr] == str[sptr]) ++sptr;
if(sptr != bNode->length) return 0;
return find(str + sptr, length - sptr, bNode);
}
return 0;
}
} t;
char allstr[10001][51], tmp[51];
int n;
int main() {
scanf("%d", &n);
for(register int i= 0; i < n; i++) {
scanf("%s", allstr[i]);
t.insert(allstr[i], strlen(allstr[i]), &t.mNode);
}
scanf("%d", &n);
for(register int i= 0, j; i < n; i++) {
scanf("%s", tmp);
j= t.find(tmp, strlen(tmp), &t.mNode);
switch(j) {
case 0: printf("WRONG\n"); break;
case 1: printf("OK\n"); break;
case 2: printf("REPEAT\n"); break;
}
}
return 0;
}最需要注意的事,要用数组保存输入的字符串,不能更改!!!
后续:
我写的常数可能挺大,希望dalao们试试各种卡常优化...
不知道能不能搞个大事情,这个字典树出名了别忘了Ciyang(出名我就女装了)
又想了一下,应该很容易改成可持久化Trie.
如果这个算法早就有人发明了告诉我一下.
希望题解能过!!!