算法理解
将一个字符串的每一位对应一个深度,每个字符对应一个节点,有一堆这样的字符串于是就构成了一棵树
如何存储树呢?
如果按照树的大小开点,有n层,一共要开 \(26^n\) 个点,一定是不行的,考虑一种类似于链表的思想,如果要开一个点,就进行编号,然后对应26条边分别存下一位的标号,注意要开 \(tr[N*26][26]\)个点,因为一共有n个字符串,n个字符串每一位都有可能不同
T1:
每遍历一个点就把它依次经过的点加1,然后统计要查询的字符串最后一个字符上对应的点权
T2:
经典字典树,我们将点转化为二进制,然后考虑,对于两个数,它们出现不同的位数越高,异或值越大,倒序将每一个数二进制存入,枚举一个数,然后遍历树,只要有和枚举数不同的叉就分,最后统计最大值
T3:
跑一边dfs统计一个节点到根的异或值 \(s[i]\) ,然后只要求出最大的 \(s[i] xor s[j]\)
标签:要开,26,然后,字符串,2.3,对应,字典 From: https://www.cnblogs.com/zcxnb/p/18439350