tangjz @ 2018-11-16 03:01:44

https://www.sciencedirect.com/science/article/pii/030439759390200D

最短公共非子序列问题在字符集大小 >= 2 的时候好像一直是NP完全？这题能做？

tangjz @ 2018-11-16 15:15:37

上面说的是：给定一个字符集 Σ，和在这个字符集上的字符串集合 L，以及一个非负整数 k，在这个字符集构成的字符串里，确定是否存在一个长度不超过 k 的字符串使得它不是任何一个 L 中字符串的子序列（子序列可以不连续），这个问题在字符集大小不小于 2 时是 NP 完全的。