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

Question

似乎许多困难的字符串算法都可以使用后缀尝试(树)和动态编程来解决。

但是我不确定什么时候使用哪种方法是最好的。

此外，在特定的算法领域掌握哪种方法更好，并在求职面试领域将其纳入您的武器库？我认为它是程序员在任何任务或类似的事情中使用频率更高的一种？

与简单地比较渐近符号相比，这更有助于掌握哪种算法技术是你工作中最常用的

Answer 1

想一想一个需要后缀数组的问题:后缀数组只是你的need...and，很容易学习解决大多数涉及后缀数组的问题的基本要素。

另一方面，DP是一种算法technique..MASTER IT，您将能够解决大量仅限problems..not的字符串。

对于一次面试，我将采访DP anyday...for面试官，DP问题让他们变得复杂，没有DP (在给定的约束下)几乎不可能解决，但解决方案意味着你给他们一个基本的递归，以及DP如何帮助你解决it.If这是一个仅限后缀数组的问题，这意味着他们评估你的是单一的数据结构(一旦学会就很容易)，而不是需要掌握的更一般的技术。

PS：我一直推迟学习DP，直到最近我厌倦了尝试使用任何高级数据结构来解决问题(需要DP )，并且总是会失败(例如：UVA 1394 --简单的问题，因为我知道如何使用DP来解决它，但是我继续学习段树，并获得O(nlgn)，而DP给了我O(n)。所以最后的建议是:如果你还没有学习过DP，那就丢掉所有其他的东西去尝试吧。

Answer 2

老实说，对于求职面试，不需要后缀树。这太难了，而且超出了范围。然而，DP在谷歌和facebook等知名公司的面试中被广泛使用。

与DP相比，后缀树在解决问题时有一定的局限性。通常用来解决字符串相关的问题。但是DP可以解决许多不同的领域。