プログラミング

この問題では、正の整数を表す数字列が1つ与えられ、桁の入れ替え（スワップ）をちょうどk回行うことで、値が最大になる並び替えを求めます。 解き方の基本は、ある桁を選び、その後ろにある桁と1つずつ入れ替えながら最大値を探索することです。この操作をk回繰り返します。ここではバックトラッキング（探索の巻き戻し）が有効に機能します。前の値より大きくならない並びを見つけたときは、元の状態に戻して別の組み合わせを試すことで、取りこぼしのない探索が可能になるからです。 入力と出力 入力: 複数桁の数字列 入力例: 129814999 出力: 桁を入れ替えて得られる最大値 出力例: 999984211 アルゴ

有限オートマトン(Finite Automata)を構築することで、テキストの中から特定のパターンをシンプルかつ効率的に検索することができます。 まず、2次元配列を埋めて有限オートマトンの遷移表(Transition Table)を作成します。この表さえ完成してしまえば、検索処理そのものは非常に単純です。オートマトンの初期状態から出発し、テキストを1文字ずつ読み進めながら状態を遷移させていき、最終状態に到達した時点で「その位置にパターンが存在する」と判断します。 計算量 有限オートマトンの構築に必要な時間計算量は O(M×K) です。ここで M はパターンの長さ、K は異なる文字の種類数(アル

カサイ（Kasai）のアルゴリズムは、接尾辞配列（サフィックスアレイ）から最長共通接頭辞（LCP：Longest Common Prefix）配列を求めるために用いられるアルゴリズムです。処理の流れとしては、まず対象の文字列から接尾辞配列を構築し、その後、その接尾辞配列を入力としてLCP配列を計算します。 そもそも接尾辞配列とは、文字列のすべての接尾辞を辞書順に並べ替えたときの開始位置（インデックス）の一覧です。また、LCP配列は隣接する接尾辞同士が共有する最長接頭辞の長さを記録したものであり、高速な文字列検索やデータ圧縮、バイオインフォマティクスなど幅広い分野で活用されています。 計算量に

Knuth–Morris–Pratt法（KMP法）は、テキストを左から右へ向かって一方向に走査しながらパターン照合を行う、高速な文字列検索アルゴリズムです。照合中に不一致が発生した際にも、それまでに一致済みだった文字の情報を捨てずに再利用するため、テキスト側の比較位置を後戻りさせる必要がありません。とくに、パターンの中に同じ部分文字列（サブパターン）が複数回現れるような場合、その性質を活かして無駄な比較を大幅に削減でき、最悪の入力に対しても安定した性能を発揮します。 その計算量は O(n)（nはテキスト長。厳密には前処理を含めて O(n + m)、mはパターン長）であり、どのような入力でも線

文字列の中から最も長い回文部分文字列を効率よく見つけたい場合、マナカーのアルゴリズム（Manachers Algorithm）が非常に有効です。この手法では、文字列内の各文字を中心として、左右のポインタを用いて回文が成立するかどうかを順に確認していきます。あわせて、回文に関する情報を記録するための補助配列を用意しておくことで、各位置における回文の長さを容易に参照できるようになります。すべての文字に対してこの処理を実行し、文字列全体の走査が完了した時点で、構築した配列から最長の回文部分文字列を特定できます。 このアルゴリズムの計算量は O(n) です。全文字を中心として毎回両方向へ展開する単純な

ナイーブパターン検索とはナイーブパターン検索（Naïve Pattern Search）は、数ある文字列探索アルゴリズムの中で最もシンプルな手法です。テキスト（対象となる主文字列）の各文字を、パターン（探したい文字列）と一つずつ照合していくことで、部分文字列を見つけ出します。このアルゴリズムには、以下のような特徴があります。事前処理（プリプロセッシング）が一切不要短いテキストに対して有効追加のメモリ領域（補助記憶域）を必要としない実装が非常に簡単で分かりやすい一方で、計算量は O(m×n)（m はパターンの長さ、n は主文字列の長さ）となるため、大規模なテキストには向いていません。効率より s

ラビン・カープ（Rabin-Karp）アルゴリズムは、テキストの中から特定のパターンを効率よく探し出すための文字列検索アルゴリズムの一つです。ナイーブな手法と同じく検索ウィンドウを1文字ずつずらしながら照合を行いますが、毎回すべての文字を比較するのではなく、まず各ウィンドウのハッシュ値を計算します。そして、ハッシュ値が一致した場合にのみ、文字単位の詳細な照合を実行します。この仕組みにより、無駄な文字比較を大幅に削減でき、検索処理が高速化されます。 平均的な時間計算量は O(m+n) ですが、ハッシュの衝突が多発するような最悪ケースでは O(mn) になる点に注意が必要です。 入力と出力 入力：

与えられた文字列からは、すべての可能な接尾辞（サフィックス）を取り出すことができます。これらの接尾辞を辞書式順序でソートすることで得られるのが「接尾辞配列」です。また、接尾辞配列は接尾辞木（サフィックスツリー）を用いて構成することも可能で、接尾辞木に対してDFS（深さ優先探索）で走査を行うことでも得られます。接尾辞配列を利用すれば、接尾辞の検索を線形時間で行えるだけでなく、二分探索に近い手法によって文字列中の部分文字列（パターン）も高速に発見できます。計算量このパターン検索アルゴリズムの時間計算量は O(m log n) です（m はパターンの長さ、n はテキストの長さ）。入力と出力入力: メ

テキストからすべての接尾辞（サフィックス）を生成し、それらを木構造（トライ木）としてまとめることができます。テキスト中に出現するあらゆるパターンは、必ずテキストのいずれかの接尾辞の接頭辞（プレフィックス）になっているという性質があります。この性質を利用し、すべての接尾辞からトライ木を事前に構築しておけば、任意の部分文字列を線形時間で検索できるようになります。各接尾辞は文字列終端記号で終わるものとして扱います。検索時には、各ノードから次の文字に対応するパスが存在すれば前方へ進み、存在しなければ「パターンは見つからない」と判断して処理を終了します。このアルゴリズムの時間計算量は O(m + k)

Zアルゴリズム（Z Algorithm）は、その名の通り「Z配列（Z Array）」を作成することで文字列検索を実現するアルゴリズムです。Z配列のサイズは主文字列（テキスト）と同じであり、各位置から始まる部分文字列のうち、文字列の先頭と一致する最長の長さを格納します。処理の最初に、パターンと主テキストを、両者に含まれない特殊な記号で連結します。パターンをP、主テキストをTとすると、連結後の文字列は P$T のようになります（ここでは $ がPにもTにも含まれていないものと仮定します）。このアルゴリズムの計算量は O(m+n) です。m はパターンの長さ、n は主文字列の長さを表します。入力と出

ハミルトン閉路（Hamiltonian Cycle）は、グラフ理論における重要な概念の一つです。無向グラフにおいて、すべての頂点をちょうど一度ずつ訪れる経路を「ハミルトン経路（Hamiltonian Path）」と呼びます。さらに、その経路の最後の頂点から最初の頂点へ戻る辺が存在する場合、この経路を「ハミルトン閉路（ハミルトンサイクル）」または「ハミルトン回路」と呼びます。本記事では、与えられたグラフがハミルトン閉路を持つかどうかを判定する問題を扱い、閉路が存在する場合にはその閉路そのものを出力するアルゴリズムを解説します。なお、この種の問題はNP完全であることが知られており、一般的にはバック

連結グラフ G(V, E) と、すべての辺の重み（コスト）が与えられたとき、クラスカルのアルゴリズム（Kruskals algorithm）は、このグラフと各辺のコストをもとに最小全域木（Minimum Spanning Tree）を求めます。クラスカル法は「マージツリーアプローチ」とも呼ばれる手法です。初期状態では各頂点がそれぞれ独立した木として存在しており、コストが最小の辺から順に選んで木同士を統合していくことで、最終的に1本の木を形成します。具体的な手順としては、まず問題のすべての辺を列挙し、コストの昇順にソートします。続いて、リストからコストの小さい辺を順に取り出して木へ追加していきま

異なる額面の硬貨のリスト C(c₁, c₂, …, Cₙ) と、両替したい金額 V が与えられたとき、V をちょうど作るために必要な硬貨の枚数を最小化する問題を「最小コイン交換問題（Minimum Coin Change Problem）」と呼びます。 前提条件： 各額面の硬貨は無限に存在するものと仮定します。 問題の概要 ここでは、硬貨の種類が {1, 2, 5, 10} の場合を考えます。各額面とも無限枚あるため、指定された金額を作るときは、できるだけ少ない枚数で構成することを目指します。 例として、金額が 22 の場合は {10, 10, 2} の 3 枚を選べばよく、これが最小枚数の組

問題の概要 列車の到着時刻と出発時刻のリストが与えられます。求めるのは、どの列車も駅で待機せずに済むようにするために必要な、プラットフォーム（ホーム）の最小数です。 すべての時刻をあらかじめソートしておけば、この問題は簡単に解けます。「駅に到着したものの、まだ出発していない列車」の数を時系列に沿って追跡することで、同時に駅に存在する列車の最大数、すなわち必要なプラットフォームの最小数が分かります。 このアルゴリズムの計算量は O(n log n) であり、その大部分はソート処理にかかるコストです。 入力と出力 入力： 到着時刻と出発時刻のリスト Arrival: {900, 940, 950,

はじめに重み付き連結グラフ G(V, E) のすべての辺にコストが与えられているとき、プリム法はこのグラフから最小全域木を見つけ出すアルゴリズムです。木を成長させるアプローチプリム法は、木を少しずつ成長させていく手法を採用しています。まず始点となる頂点を選び、そこから隣接する頂点の中で最もコストの低い辺を順番に選びながら、木を一つずつ拡張していきます。具体的には、次の図のようなグラフを例として考えます。基本的な考え方：2つの集合による管理この問題は、2つの集合を使って効率的に解くことができます。選択済み集合：すでに木に含まれた頂点を管理します。未考慮集合：まだ木に追加されていない頂点を管理しま

このアルゴリズムは、前回紹介した隣接行列版のプリム法と基本的な流れは同じですが、唯一異なる点は、グラフ G(V, E) を隣接リストで表現しているところです。 隣接リスト表現を用いた場合の時間計算量は O(E log V) です。辺の数 E が頂点数 V に比べて少ない「疎なグラフ」では、隣接行列を使う O(V²) の実装よりも効率的に動作します。 プリム法とは、重み付き無向グラフから最小全域木（Minimum Spanning Tree：MST）を求める代表的な貪欲法アルゴリズムの一つです。本実装では、すでに木に組み込まれた頂点の集合を B、グラフの全頂点の集合を N として管理し、B と

フラクショナルナップサック問題とは フラクショナルナップサック問題では、それぞれ固有の「価値」と「重さ」を持つ品物のリストが与えられます。最大積載重量 W のナップサックに対して、総重量が W を超えない範囲で品物を選び、合計価値を最大化することが目的です。 ナップサック問題には2種類ある 0–1ナップサック問題：品物を分割できないため、入れるか入れないかの二択になります。 フラクショナルナップサック問題：品物を小さく分割できるため、一部だけを詰め込むことも可能です。 本記事では、後者のフラクショナルナップサック問題を取り上げます。この問題は貪欲法（グリーディ法）で必ず最適解が得られるこ

Aho-Corasickアルゴリズムは、複数のキーワード（パターン）をテキスト内で同時に検索するための効率的な辞書照合アルゴリズムです。トライ木（プレフィックスツリー）とオートマトンの概念を組み合わせることで、テキストの長さに対して線形時間 O(N + L + Z) で全てのキーワードの出現位置を見つけ出せます。ここで N はテキスト長、L は全キーワードの総文字数、Z はマッチ数を表します。 アルゴリズムの3つのフェーズ Aho-Corasickアルゴリズムは以下の3段階で構成されます。 Go-to（遷移）フェーズ：全キーワードからトライ木を構築し、文字ごとの状態遷移を定義します。

アナグラムとは、ある文字列やパターンに含まれる文字を並べ替えることで作れる、すべての順列のことを指します。通常のパターン検索では、パターンそのものと完全に一致する部分のみを探します。一方、アナグラムパターン検索はこれとは少し異なり、テキスト中に現れる「指定パターンのあらゆる並べ替え」をすべて検索対象とします。 アナグラムパターン検索の基本的な考え方 この問題を解くためには、テキスト全体を「パターンと同じ長さのウィンドウ」に分割して考えます。まず、パターンに含まれる各文字の出現回数を数え、配列に記録します。次に、各ウィンドウについても同じように出現頻度配列を作成し、両方の配列が一致しているかどう

不良文字ヒューリスティックとは 不良文字ヒューリスティック（Bad Character Heuristic）は、文字列検索アルゴリズムの一つであるボイヤー・ムーア法（Boyer-Moore Algorithm）で用いられる手法のひとつです。ボイヤー・ムーア法には、このほかに「良好接尾辞ヒューリスティック（Good Suffix Heuristic）」というアプローチもあります。 この手法では、テキスト（主文字列）側の文字のうち、パターンと一致しない文字、すなわち「不良文字（Bad Character）」を見つけます。不一致が発生した場合、その不一致箇所が一致するようにパターン全体をシフトします