KMP algorithm

/keɪ em piː ˈælɡərɪðəm/ ケイエムピー アルゴリズム

1. クヌース-モリス-プラット法（KMP法）は、文字列の中から特定のパターン（部分文字列）を効率的に検索するためのアルゴリズムです。

検索対象のテキストと検索するパターン文字列を比較する際に、パターン自体に繰り返し構造があることを利用して、無駄な比較をスキップし、高速な検索を実現します。このアルゴリズムは、特に長いテキストの中で短いパターンを検索する際に非常に有効です。

The KMP algorithm is a fundamental concept in computer science for string matching. (KMPアルゴリズムは、文字列照合におけるコンピュータサイエンスの基本的な概念です。)

• The KMP algorithm: クヌース-モリス-プラット法という特定のアルゴリズムを指します。
• is a fundamental concept: 「基本的な概念である」という意味です。
• in computer science: コンピュータサイエンスの分野において、という意味です。
• for string matching: 文字列照合のために、または文字列照合に関して、という意味です。

You need to understand how the KMP algorithm works to solve this problem efficiently. (この問題を効率的に解決するには、KMPアルゴリズムがどのように機能するかを理解する必要があります。)

• You need to understand: 「あなたは理解する必要がある」という表現です。
• how the KMP algorithm works: KMPアルゴリズムがどのように機能するか、という意味です。
• to solve this problem: この問題を解決するために、という意味です。
• efficiently: 効率的に、という副詞です。

The KMP algorithm avoids re-examining characters in the text that have already been matched. (KMPアルゴリズムは、すでに照合されたテキスト中の文字を再調査することを避けます。)

• The KMP algorithm: クヌース-モリス-プラット法という特定のアルゴリズムを指します。
• avoids re-examining: 「再調査することを避ける」という動詞句です。
• characters in the text: テキスト中の文字、という意味です。
• that have already been matched: すでに照合された、という関係代名詞節で先行詞のcharactersを修飾しています。

Learning the KMP algorithm is often part of advanced data structures and algorithms courses. (KMPアルゴリズムを学ぶことは、高度なデータ構造とアルゴリズムのコースの一部であることがよくあります。)

• Learning the KMP algorithm: KMPアルゴリズムを学ぶこと、という動名詞句です。
• is often part of: 「～の一部であることが多い」という表現です。
• advanced data structures and algorithms courses: 高度なデータ構造とアルゴリズムに関するコース、という意味です。

Implementations of the KMP algorithm can be found in various programming language libraries. (KMPアルゴリズムの実装は、様々なプログラミング言語ライブラリで見つけることができます。)

• Implementations of: ～の実装、という意味です。
• the KMP algorithm: クヌース-モリス-プラット法という特定のアルゴリズムを指します。
• can be found: 「見つけることができる」という受動態の表現です。
• in various programming language libraries: 様々なプログラミング言語のライブラリの中に、という意味です。

関連

• String matching
• Algorithm
• Computer science
• Text search
• Pattern matching
• Data structures
• Knuth-Morris-Pratt