我成了五个大佬的祖宗_我家可能有位大佬

原题解地址及本文目的

https://ciyang.blog.luogu.org/solution-p2580

本文目的：留作日后自用，翻译一下大佬清奇的码风。

正文

Lumpy_Trie是边压缩的Trie， 可以省空间， 各Node存的是字符串。

现在来翻译（解释及简化(我是懒癌)）一下Ciyang的源码。（源码及原注释在Ciyang神犇的题解里， 这里的注释是我自己加的， 这里的码是我抄的， 不保证完全一致）

先翻译节点定义

//这是Ciyang的define #define clear(a) memset(a, 0, sizeof a) #define copy(a, b) memcpy(a, b, sizeof a) //这是Ciyang的节点定义 char allstr[10001][51];//这是Ciyang的腐竹内存 char tmp[51];//这是本文中不会用到的东西 struct Lumpy_Tnode { const char *pStr;//指针，指向辅助内存中的地址，即各Node保存的字符串都是存在腐竹内存中的 int length, isEnd;//length就是本节点中存的字符串的长度，即pStr后多少位， isEnd就和Trie的“终结标记”一样（isEnd的定义浅显易懂 Lumpy_Tnode *children[26];//这是子节点，像Trie一样， 存储后继节点的地址 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;//这个我想是 main Node， 即 root Node 

接下来翻译insert函数

//这个函数在主程序里这样调用 insert(要插入的串， 要插入的串的长度， mNode（root）); inline void insert(const char *str, int length, Lumpy_Tnode *bNode) { //bNode是当前节点， 和Trie完全一样， str就是指针啦 if(!length) { bNode->isEnd = 1; return; } //建议先看后面的翻译 int ch = str[0] - 'a';//这个就是懒癌的象征了， 当然确实快 if(bNode->children[ch]) { //已经存在以 str[0] 为首字母的后继子串，请看下面翻译 bNode = bNode->children[ch];//转移焦点，开始协调 register int sptr = 0;//指针 while(sptr < length && sptr < bNode->length//循环来找当前字符串和节点存储的字符串最长前缀（Ciyang的注释 && bNode->pStr[sptr] == str[sptr] ) ++sptr; if(sptr != bNode->length) { //当节点存储的字符串不是插入字符的子串时……（由上面那个while的结束条件表明 //于是就要将最大公共前缀变成此节点， 两个后缀都变成子节点 Lumpy_Tnode *nNode = new Lumpy_Tnode(bNode->pStr + sptr, bNode->length - sptr, bNode->isEnd); //上一行那句就是讲此节点的后缀拆一出来作为子节点，此时原节点的子节点信息应被继承 copy(nNode->children, bNode->children); // 这就是继承了， 为什么继承大家都清楚 bNode->isEnd = 0, bNode->children[bNode -> pStr[sptr] - 'a'] = nNode; //此时新节点要接到父节点上 } //以下应该是代码的简化， 如果想看的清楚明白一点就把以下代码加个完全复制到上面那个if里； bNode->length = sptr; insert(str+sptr, length - sptr, bNode); //将去掉与原bNode公共前缀的str插入 } else//并不存在以 str[0] 为首字母的后继子串（第一次的象征 bNode->children[ch] = new Lumpy_Tnode(str, length, 1); //于是就要新建节点， 并把整个串当数据 return; }

以下翻译find函数（简单多了

inline int find(const char *str, int length, Lumpy_Tnode *bNode) { if(!length) { 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; //自带剪枝,若当前查找字符串长度小于当前公共前缀,那么字典树中不存在当前查找的字符串（Ciyang的注释 //好吧， 我的解释：当前查找的字符串若存在（被插入过）， 那么公共前缀一定比当前串长短或等长 register int sptr = 0; while(sptr < bNode->length && bNode->pStr[sptr] == str[sptr]) ++sptr; if(sptr != bNode->length) return 0; //最长公共前缀必须是当前查找的字符串的子串(Ciyang的注释） // 即……好吧看while条件吧，写不下去了 return find(str+sptr, length-sptr, bNode); //无需解释（写不下去了啊啊啊 } //这里可以加个else，更浅显 return 0; } 

以下是以我的码风（受Ciyang影响极深， 并认为Ciyang马蜂简洁的我的马蜂）抄写的Ciyang代码（luogu P2580

#include<bits/stdc++.h> using namespace std; #define clear(a) memset(a, 0, sizeof a) #define copy(a, b) memcpy(a, b, sizeof a) struct node{ const char *Sp; int len, isEnd; node *ch[26]; node() { Sp = 0, len = isEnd = 0, clear(ch); } node(const char *str, int length, int end) { Sp = str, len = length, isEnd = end, clear(ch); } } root; char AllStr[10001][60], s[60]; void insert(const char *str, int length, node* u) { if(!length) { u->isEnd = 1; return; } int v = str[0] - 'a'; if(u->ch[v]) { u = u->ch[v]; register int sptr = 0; while(sptr < u->len && sptr < length && str[sptr] == u->Sp[sptr]) ++sptr; if(sptr != u->len) { node *nNode = new node(u->Sp + sptr, u->len - sptr, u->isEnd); copy(nNode->ch, u->ch), clear(u->ch); u->isEnd = 0, u->ch[u->Sp[sptr] - 'a'] = nNode; } u->len = sptr; insert(str+sptr, length - sptr, u); } else u->ch[v] = new node(str, length, 1); return; } int find(const char *str, int length, node* u) { if(!length) { if(u->isEnd == 1) return u->isEnd++; return u->isEnd; } int v = str[0] - 'a'; if(u->ch[v]) { u = u->ch[v]; if(length < u->len) return 0; register int sptr = 0; while(sptr < u->len && str[sptr] == u->Sp[sptr]) ++sptr; if(sptr != u->len) return 0; return find(str + sptr, length - sptr, u); } return 0; } int main() { int n, m; scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%s", AllStr[i]); insert(AllStr[i], strlen(AllStr[i]), &root); } scanf("%d", &m); for(int i = 1; i <= m; ++i) { scanf("%s", s); switch(find(s, strlen(s), &root)) { case 0: cout << "WRONG\n";break; case 1: cout << "OK\n";break; case 2: cout << "REPEAT\n";break; } } return 0; }