请问在对 lms 子串进行离散化的过程中,为什么会出现两个 lms 子串所有位置字符相等但某个位置后缀类型(S 或 L)不同的情况?
我认为不会出现的理由:两个字符相等的位置如果后面出现和他们不同的字符,那么那个字符会把他们变成(S 或 L),例如 aaaab 中 b 使得这几个 a 一定是 S 型,两个子串的这一位置应该都是 S 型。而如果后面的字符都一样,则后面一串都是一个类型,但除了最后哨兵字符单独出来的 lms 子串,所有 lms 子串最后两个字符的类型都分别是 L 和 S,显然不能后面一串都一样。综上所述,不论当两个相同字符后面出现相同或不同的字符,这两个字符的类型都得相同。
如果上面的话是对的,是不是在离散化 lms 子串的过程中无需判断字符类型也能保证正确性与复杂度?
附上一份 在 LOJ 上测试的,将 shadowice1984 日报中的代码去掉上述判断仍然通过 的记录。