プログラミング

Knuth Morris Pratt（KMP）は、文字を左から右にチェックするアルゴリズムです。パターンにサブパターンが複数存在する場合、最悪の場合でも、そのプロパティを使用して時間計算量を改善します。 KMPの時間計算量はO（n）です。 入力と出力 Input: Main String: “AAAABAAAAABBBAAAAB”, The pattern “AAAB” Output: Pattern found at location: 1 Pattern found at location: 7 Pattern found at locat

文字列から最長の回文部分文字列を見つけるには、Manacherのアルゴリズムを使用できます。各文字を選択することにより、左右のポインタを使用して回文があるかどうかを見つけようとします。情報を格納する別の配列があります。その情報から、回文の長さを簡単に見つけることができます。文字ごとに、配列は情報を格納します。文字列全体をトラバースした後、作成された配列から最長のパリンドロームサブシーケンスを見つけることができます。 このアルゴリズムの時間計算量はO（n）です。 入力と出力 Input: String: “levelup” Output: Longest palindr

ナイーブパターン検索は、他のパターン検索アルゴリズムの中で最も簡単な方法です。パターンに対するメイン文字列のすべての文字をチェックします。このアルゴリズムは、小さいテキストに役立ちます。前処理フェーズは必要ありません。文字列を1回チェックすることで、部分文字列を見つけることができます。また、操作を実行するための余分なスペースを占有しません。 ナイーブパターン検索法の時間計算量はO（m * n）です。 mはパターンのサイズ、nはメインストリングのサイズです。 入力と出力 Input: Main String: “ABAAABCDBBABCDDEBCABC”, patte

Rabin-Karpは、より効率的な方法でパターンを見つけるためのもう1つのパターン検索アルゴリズムです。また、ウィンドウを1つずつ移動してパターンをチェックしますが、すべての場合にすべての文字をチェックせずに、ハッシュ値を見つけます。ハッシュ値が一致すると、それだけが各文字をチェックしようとします。この手順により、アルゴリズムがより効率的になります。 時間計算量はO（m + n）ですが、最悪の場合はO（mn）です。 入力と出力 Input: Main String: “ABAAABCDBBABCDDEBCABC”, Pattern “ABC”

指定された文字列から、可能なすべてのサフィックスを取得できます。辞書式順序で接尾辞を並べ替えると、接尾辞配列を取得できます。接尾辞配列は、接尾辞木を使用して形成することもできます。接尾辞木のDFSトラバーサルを使用することにより、接尾辞配列を取得できます。接尾辞配列は、線形時間で接尾辞を見つけるのに役立ちます。二分探索タイプの手順を使用して、接尾辞配列を使用して部分文字列を検索することもできます。 時間計算量はO（m log n） 入力と出力 Input: Main String: “BANANA”, Pattern: “NAN” Output

テキストから、すべてのサフィックスを生成してツリー構造を作成できます。テキストに表示されるすべてのパターンは、テキストで可能な接尾辞の1つの接頭辞でなければならないことを私たちは知っています。すべての接尾辞のTrieを作成することにより、線形時間で任意の部分文字列を見つけることができます。すべての接尾辞は、文字列終了記号で終わります。パスがある場合は各ノードから前方に移動し、そうでない場合はパターンが見つからないことを返します。 このアルゴリズムの場合、時間計算量はO（m + k）です。ここで、mは文字列の長さ、kはテキスト内のパターンの頻度です。 入力と出力 Input: Main Str

このアルゴリズムでは、Z配列を作成する必要があるため、このアルゴリズムはZアルゴリズムと呼ばれます。 Z配列のサイズは、テキストサイズと同じです。この配列は、メイン文字列の現在の文字から始まる可能な最長のサブ文字列の長さを格納するために使用されます。最初に、パターンと本文は、テキストとパターンに存在しない特別な記号で連結されます。 Pがパターンで、Tが本文の場合、連結後はP $ Tになります（$がPとTに存在しないと仮定します）。 このアルゴリズムの場合、mはパターンの長さ、nはメイン文字列の長さであるため、時間計算量はO（m + n）です。 入力と出力 Input: Main String

無向グラフでは、ハミルトン経路は各頂点を1回だけ訪問する経路であり、ハミルトン閉路または回路は最後の頂点からのエッジがあるハミルトン経路です。最初の頂点に。 この問題では、グラフにハミルトン閉路が含まれているかどうかを判断しようとします。また、ハミルトン閉路が存在する場合は、その周期も印刷します。 入力と出力 Input: The adjacency matrix of a graph G(V, E). Output: The algorithm finds the Hamiltonian path of the given graph. For this case it is (0, 1

連結グラフG（V、E）があり、すべてのエッジの重みまたはコストが示されています。クラスカルのアルゴリズムは、グラフとコストを使用して最小全域木を見つけます。 これは、マージツリーアプローチです。最初はさまざまなツリーがありますが、このアルゴリズムは、コストが最小のエッジを取得することでそれらをマージし、単一のツリーを形成します。 この問題では、すべてのエッジがリストされ、コストに基づいて並べ替えられます。リストから、最小コストのエッジが取り出されてツリーに追加され、エッジ形成サイクルかどうかがチェックされます。サイクルを形成する場合は、リストからエッジを破棄して次のエッジに進みます。

コインC（c1、c2、……Cn）のリストがあり、値Vも指定されています。ここで問題となるのは、チャンスをVにするために最小数のコインを使用することです。 注- コインの数が無限であると仮定しますC この問題では、異なるコインのセットC {1、2、5、10}が与えられていると考えます。各タイプのコインは無限にあります。要求された値を変更するために、あらゆる種類のコインの最小数を取得しようとします。 例として、値22の場合、最小値として{10、10、2}、3コインを選択します。 このアルゴリズムの時間計算量idO（V）、ここでVは値です。 入力と出力 Input: A value, say

到着時刻と出発時刻のリストが表示されます。ここで問題となるのは、列車が待たないため、鉄道に必要なプラットフォームの最小数を見つけることです。 すべてのタイミングを並べ替えて並べ替えることで、解決策を簡単に見つけることができます。電車が駅に到着したが駅を出ていないときを追跡するのは簡単です。 この問題の時間計算量はO（n Log n）です。 入力と出力 Input: Lists of arrival time and departure time. Arrival: {900, 940, 950, 1100, 1500, 1800} Departure: {910, 1200, 1120,

連結グラフG（V、E）があり、すべてのエッジの重みまたはコストが示されています。プリムのアルゴリズムは、グラフGから最小全域木を見つけます。 それは成長する木のアプローチです。このアルゴリズムでは、ツリーを開始するためにシード値が必要です。シード頂点は、ツリー全体を形成するように成長します。 この問題は、2つのセットを使用して解決されます。 1つのセットには、すでに選択されているノードが保持され、別のセットには、まだ考慮されていないアイテムが保持されます。シード頂点から、最小エッジコストに基づいて隣接する頂点を取得するため、ノードを1つずつ取得してツリーを成長させます。 この問題の

これは前のアルゴリズムに似ています。ここでの唯一の違いは、グラフG（V、E）が隣接リストで表されることです。 時間計算量隣接リストの表現はO（E log V）です。 入力と出力 Input: The cost matrix: Output: Edge: A--B And Cost: 1 Edge: B--E And Cost: 2 Edge: A--C And Cost: 3 Edge: A--D And Cost: 4 Edge: E--F And Cost: 2 Edge: F--G And Cost: 3 Total Cost: 15 アルゴリズム prims(g: Graph, s

アイテムのリストが表示されます。各アイテムには独自の値と重みがあります。アイテムは、最大重量制限がWのナップザックに入れることができます。問題は、W以下の重量を見つけて、値を最大化することです。 ナップサック問題には2つのタイプがあります。 0 –1ナップザック フラクショナルナップザック 0〜1のナップザックの場合、アイテムを小さなピースに分割することはできません。また、フラクショナルナップザックの場合、アイテムを小さなピースに分割することもできます。 ここでは、分数ナップサック問題について説明します。 このアルゴリズムの時間計算量はO（n Log n）です。 入力と出力 In

このアルゴリズムは、指定されたすべてのキーワードセットのすべての出現箇所を見つけるのに役立ちます。これは一種の辞書照合アルゴリズムです。すべてのキーワードを使用したツリー構造を使用します。ツリーを作成した後、線形時間で検索を行うために、ツリーをオートマトンとして変換しようとします。 Aho-Corasickアルゴリズムには3つの異なるフェーズがあります。 これらはGo-to、Failure、 および出力 。移行段階では、すべてのキーワードを使用してツリーを作成します。次のフェーズまたは失敗フェーズでは、いくつかのキーワードの適切なサフィックスを取得するために、後方遷移を見つけようとします。

アナグラムは基本的に、特定の文字列またはパターンのすべての順列です。このパターン検索アルゴリズムは少し異なります。この場合、正確なパターンが検索されるだけでなく、テキスト内の指定されたパターンのすべての可能な配置が検索されます。 この問題を解決するために、テキスト全体をパターンと同じ長さのいくつかのウィンドウに分割します。次に、パターンの各文字が検出され、配列に格納されます。また、ウィンドウごとに、カウント配列を見つけて、それらが一致しているかどうかを確認します。 アナグラムパターン検索アルゴリズムの時間計算量はO（n）です。 入力と出力 Input: The main String &l

悪い文字のヒューリスティック手法は、ボイヤームーアアルゴリズムのアプローチの1つです。もう1つのアプローチは、GoodSuffixHeuristicです。この方法では、パターンと一致しないメイン文字列の文字を意味する不正な文字を見つけようとします。不一致が発生した場合は、不一致が一致するまでパターン全体をシフトします。一致しない場合は、パターンが不良文字を超えて移動します。 ここで、時間計算量は、最良の場合はO（m / n）、最悪の場合はO（mn）です。ここで、nはテキストの長さ、mはパターンの長さです。 入力と出力 Input: Main String: “ABAAABCDBBA

これはボイヤームーアアルゴリズムのもう1つのアプローチです。グッドサフィックスヒューリスティックメソッドと呼ばれることもあります。この場合、前処理テーブルがサフィックステーブルとして作成されます。この手順では、パターンの最後の文字から部分文字列またはパターンが検索されます。メイン文字列のサブストリングがパターンのサブストリングと一致すると、一致したサブストリングの他のオカレンスを見つけるために移動します。また、メイン文字列のサフィックスであるパターンのプレフィックスを見つけるために移動することもできます。それ以外の場合は、パターンの全長を移動します。 入力と出力 Input: Main Str

クイックソート手法は、リストを2つの部分に分割することによって行われます。最初に、ピボット要素は分割アルゴリズムによって選択されます。ピボットの左側の部分はピボットよりも小さい値を保持し、右側の部分は大きい値を保持します。分割後、それぞれの個別のリストは同じ手順を使用して分割されます。 クイックソート手法の複雑さ 時間計算量：最良の場合と平均的な場合はO（n log n）、最悪の場合はO（n ^ 2）。 スペースの複雑さ：O（log n） 入力と出力 Input: The unsorted list: 90 45 22 11 22 50 Output: Array before Sorti

基数ソートは、非比較のソートアルゴリズムです。この並べ替えアルゴリズムは、同じ位置と値を共有する数字をグループ化することにより、整数キーで機能します。基数は、記数法のベースです。 10進法では、基数または基数は10であることがわかっているので、いくつかの10進数を並べ替えるには、数値を格納するために10個の位置ボックスが必要です。 基数ソート手法の複雑さ 時間計算量：O（nk） スペースの複雑さ：O（n + k） 入力と出力 Input: The unsorted list: 802 630 20 745 52 300 612 932 78 187 Output: Data before