关于Z函数与不同子串计数的疑问:被广泛传播的算法是否存在问题?
关于Z函数统计不同子串数量的困惑
我并不是资深数学爱好者,所以可能存在理解上的疏漏,但我想拿Z函数算法来做个测试——就用字符串baz为例。这个字符串的不同子串集合很明确:{'b','a','z', 'ba', 'az', 'baz'},一共6个。
不过我按照自己的理解走Z函数的流程时,却得到了和预期完全不符的结果:
- 初始是空字符串,添加字符
b后,根据算法定义,长度为1的字符串的z[0]为0(这个位置本身无定义); - 接着把
b和a拼接成ba,再反转成ab,计算Z函数得到{0, 0}。按照Z函数的定义,第i个元素表示从位置i开始与字符串前缀匹配的最大字符数:对于i=1的位置,字符是b,而字符串前缀是a,二者不匹配,所以z[1]=0; - 后续步骤我重复这个逻辑操作,最后得到的是全0的z数组,这和实际存在6个不同子串的情况完全对不上。
我现在有几个疑问:
- 是不是我对Z函数的工作流程存在理解误区?
- 明明很多网站都推荐用Z函数统计不同子串数量,为啥实际测试得不到正确结果?
- 难道是我误解了“不同子串”的定义?
内容的提问来源于stack exchange,提问作者Zeks
相关产品推荐
相关产品推荐

