ファイル内文字列検索におけるKMPアルゴリズムの実装
KMPアルゴリズムによるパターン検索
本記事では、KMP(Knuth-Morris-Pratt)アルゴリズムを用いたファイル内文字列検索の実装について説明します。この実装はfindstrコマンドのような機能を提供し、ディレクトリの再帰的な走査やパターンマッチングを含みます。
ヘッダーファイル (findstr.h)
#ifndef _FIND_STR_H_
#define _FIND_STR_H_
#ifdef __cplusplus
extern "C" ...
8月8日 09:59 投稿
トライ木（Trie木）の基礎と応用
基本概念
トライ木（Trie木）は文字列に関連するデータ構造で、辞書木または接頭辞木とも呼ばれます。その主な思想は「空間で時間を換える」ことです。大量の文字列を統計、ソート、または保存するために使用できます。検索する文字列をsとすると、トライ木の単一クエリの複雑度はO(|s|)です。
01トライ木は、XOR関連問題を扱うデータ構造のバリエーションです。複数の数 ...
8月3日 03:10 投稿
LeetCode 28 と 459 の解法：KMPアルゴリズムの実装と応用
LeetCode 28: 文字列の中で最初に一致するインデックスを検索する
問題リンク: 28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
KMPアルゴリズムを使用して、部分文字列を効率的に検索します。ここでは、失敗時のバックトラックテーブル（Next/LPS配列）を構築し、メイン文字列とパターンを比較します。
Python実装例
class Solution:
def build_lps(self, pa ...
7月8日 19:57 投稿
KMPアルゴリズムにおけるnext配列の最適化手法
KMPアルゴリズムのnext配列最適化
KMP（Knuth-Morris-Pratt）アルゴリズムでは、パターン文字列の部分一致情報を格納したnext配列を用いて、主文字列との照合時に不要な比較をスキップする。しかし、標準的なnext配列には冗長な比較が含まれる場合があるため、これをさらに最適化することが可能である。
最適化が必要なケース1
例えば、パターン文字列の先頭文字と現在の ...
5月26日 08:16 投稿
KMPアルゴリズムによる高速文字列検索
文字列検索問題は、与えられたテキスト文字列 S の中にパターン文字列 P が出現する位置をすべて求める課題である。ナイーブな実装では、各位置から一致を確認し、最悪計算量は O(|S| \cdot |P|) となる。
これを効率化するために、KMP（Knuth-Morris-Pratt）アルゴリズムが用いられる。このアルゴリズムは、マッチング失敗時に無駄な比較を省略することで、線形時間 O(|S ...
5月20日 08:15 投稿
トライ木：効率的な文字列検索と接頭辞マッチングのためのデータ構造
トライ木（Trie）は、辞書木や接頭辞木とも呼ばれるデータ構造で、特定の文字列が存在するかどうかの検索や、特定の接頭辞を持つ文字列の数を効率的に数えるために使用されます。
トライ木は接頭辞の概念を利用しており、各文字列を一文字ずつ分解して木構造のノードに格納します。例えば、"cup", "apple", "cake", "app", "blog" という単語がある場合、以下のような木構 ...
5月19日 06:24 投稿