問題タブ [longest-prefix]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - Trie データ構造を使用して、考えられるすべての部分文字列の LCP の合計を見つける方法は?
問題の説明:
参考文献:文字列の楽しみ方
問題の説明に基づいて、すべての可能な部分文字列 (特定の文字列) のLCPの長さの合計を見つける単純なアプローチは次のとおりです。
LCP に関するさらなる読書と調査に基づいて、Triesと呼ばれる高度なデータ構造を使用して LCP を効率的に見つける方法を指定するこのドキュメントを見つけました。次のように、Trie と Compressed Trie (Suffix Tree) を実装しました。
私の質問は、LCP の長さを見つける方法です。分岐ノードでラベル フィールドを取得することで LCP を取得できますが、考えられるすべての部分文字列の LCP の長さをどのように数えますか?
私が考えた1つの方法は、分岐ノード、LCPを保持するそのラベルフィールド、および分岐ノードの子を使用して、すべてのLCPの長さの合計を見つける方法でした(最小共通祖先?)。しかし、私はまだ混乱しています。どうすればさらに進むことができますか?
注:この問題に対する私のアプローチが間違っている可能性もあります。そのため、この問題に対して他の方法も提案してください (時間と空間の複雑さを考慮して)。
同様の未回答の質問へのリンク:
コードと理論の参考文献:
アップデート1:
@Adarsh Anuragの回答に基づいて、トライデータ構造の助けを借りて次の実装を考え出しました。
Trie 構造から変数を削除しisEndOfWord、代わりにcounter. この変数は、重複文字を含む文字列の LCP をカウントするのに役立つ重複部分文字列を追跡します。ただし、上記の実装は、個別の文字を含む文字列に対してのみ機能します。重複文字に対して @Adarsh が提案する方法を実装しようとしましたが、どのテスト ケースも満たしていません。
アップデート2:
@Adarshからのさらに更新された回答と、さまざまなテストケースでの「試行錯誤」に基づいて、重複した文字について少し進んだようですが、それでも期待どおりに機能しません。これがコメント付きの実装です。
また、ここにいくつかのサンプル テスト ケース (期待される出力) があります。
上記の実装は、テストケース 2 および 3 で失敗します (部分的な出力)。これを解決する方法を提案してください。この問題に対する他のアプローチも問題ありません。
python - 最長共通プレフィックス
文字列の配列の中から最も長い共通プレフィックス文字列を見つける関数を作成します。共通プレフィックスがない場合は、空の文字列 "" を返します。例: 入力: strs = ["flower","flow","flight"] 出力: "fl" 私はコーディングが初めてで、この問題を (leetcode から) 解決しようとしています。私の方法は、文字列間の最短文字列を検索することです。これが私のコードです。どこで間違ったのかわかりません。while ループがまったく機能しないようです。誰かが私を助けてくれれば幸いです。ここに私のコードがあります:
入力: ["花","流れ","飛行"] 出力: "flo" 予想される出力: "fl"