string - 后缀尝试与字符串算法的动态规划

Question

似乎许多困难的字符串算法都可以使用后缀尝试(树)和动态规划来解决。
但我不确定哪种方法最好使用以及何时使用。
此外，哪种方法更适合掌握算法的特定领域，并将其用于求职面试领域？我想它会是程序员在任何任务或类似任务中更频繁使用的那个吗？
与简单地比较渐近符号相比，这更多的是掌握哪种算法技术更有用，因为它在您的工作中最常使用

Answer 1

想一想需要 Lexicographically nth substring of a given string 的问题:后缀数组正是您所需要的......而且很容易学习解决涉及后缀数组的大多数问题的基本要素......
另一方面，DP 是一种算法技术。掌握它，你将能够解决大量问题......不仅是字符串。
对于面试，虽然我每天都会参加 DP...对于面试官来说，DP 问题让他们变得棘手，如果没有 DP(在给定的限制内)几乎不可能解决，但解决方案意味着你给他们一个基本的递归以及如何DP 帮助您解决它。如果这是一个仅后缀数组的问题，这意味着他们正在评估您的单一数据结构(一旦学会就很容易)，而不是需要掌握的更通用的技术。

PS:我一直推迟学习 DP，直到最近我厌倦了尝试使用任何高级数据结构解决问题(需要 DP)并且总是会失败(恰当的例子:UVA 1394 - - 一个简单的问题，现在我知道如何使用 DP 来解决它，而是继续研究线段树并获得了 O(nlgn) 而 DP 给了我 O(n)。所以最后的建议:如果没有研究过 DP，请放弃一切否则就去做吧。