string - 文字列アルゴリズムの接尾辞の試行と動的計画法の比較

Question

多くの難しい文字列アルゴリズムは、接尾辞の try(trees) と動的計画法の両方を使用して解決できるようです。
しかし、どのアプローチをいつ使用するのが最適かはわかりません。
さらに、アルゴリズムの特定の領域を習得し、就職の面接の領域でそれを武器にするのに適したアプローチはどれですか? プログラマーがタスクなどでより頻繁に使用するものになると思いますか?
これは、単純に漸近表記法を比較するよりも、仕事で最も頻繁に使用するアルゴリズム手法を習得するのに役立ちます。

Answer 1

与えられた文字列の辞書式に n 番目の部分文字列を必要とする問題を考えてみてください: 接尾辞配列はまさにあなたが必要としているものです...そして、接尾辞配列を含むほとんどの問題を解決するための基本的なことを学ぶのは簡単です..
一方、DP はアルゴリズム技術..それをマスターすれば、文字列だけでなく、膨大な数の問題を解決できるようになります。
面接ではいつでもDPを取ります...面接担当者にとって、DPの問題により、DPなしで（与えられた制約内で）解決することはほとんど不可能ですが、解決策は、基本的な再帰と方法を与えることを意味しますDPはそれを解決するのに役立ちます.それが接尾辞配列のみの問題である場合、彼らは単一のデータ構造ではなく、単一のデータ構造（一度学べば簡単）であなたを評価していることを意味します.熟達を必要とするより一般的な技術。

PS : 高度なデータ構造を使用して (DP が必要な) 問題を解決しようとしてうんざりし、常に失敗するようになった最近まで、DP の学習を延期していました (適切な例: UVA 1394 - 方法がわかった今では簡単な問題です) 。 DPを使用してそれを解決しますが、代わりにセグメントツリーを研究し、DPが私にO(n)を与えたのに対し、O(nlgn)を達成しましたしたがって、最後のアドバイス:DPを研究していない場合は、他のすべてをドロップしてそれを試してください.

Answer 2

正直なところ、就職の面接では接尾辞ツリーは必要ありません。それは難しすぎて範囲を超えています。ただし、DP は、Google や Facebook などの有名企業のインタビューで広く使用されています。

サフィックス ツリーは、DP と比較して問題を解決するための制限があります。通常、文字列関連の問題を解決するために使用されます。しかし、DP はさまざまな分野を解決できます。