string - 后缀尝试与字符串算法的动态编程

Question

似乎许多困难的字符串算法都可以使用后缀尝试（树）和动态编程来解决。
但我不确定哪种方法最好使用以及何时使用。
此外，哪种方法更能更好地掌握算法的特定领域，并将其纳入工作面试领域的武器库中？我认为这将是程序员在任何任务或类似任务中更频繁使用的那个？
这比简单地比较渐近符号更能掌握在你的工作中最常用的算法技术

Answer 1

考虑一个需要给定字符串的字典序第 n 个子字符串的问题：后缀数组正是您所需要的……并且很容易学习解决涉及后缀数组的大多数问题的基本要素。
另一方面，DP 是一个算法技术..掌握它，您将能够解决大量问题..不仅仅是字符串。
对于面试，尽管我每天都会接受 DP ......对于面试官来说，DP 问题让他们变得棘手，如果没有 DP（在给定的限制范围内）几乎不可能解决，但解决方案意味着你给他们一个基本的递归以及如何DP 可以帮助您解决它。如果它是一个仅后缀数组的问题，这意味着他们正在通过单个数据结构（一旦学会就容易）而不是需要掌握的更通用的技术。

PS：我一直推迟学习 DP，直到最近我厌倦了尝试使用任何高级数据结构解决问题（需要 DP）并且总是会失败（例如：UVA 1394——现在我知道如何解决的简单问题使用 DP 解决它，而是继续研究分段树并实现了 O(nlgn)，而 DP 给了我 O(n)。所以最后的建议：如果一个人还没有研究过 DP，那么放弃其他一切并继续努力。

Answer 2

老实说，对于工作面试，不需要后缀树。这太难了，超出了范围。然而，DP被广泛用于谷歌和Facebook等一些著名公司的采访中。

与 DP 相比，后缀树在解决问题上存在局限性。通常用于解决字符串相关的问题。但是DP可以解决很多不同的领域。