テキスト T = "ANPANMAN" に対して k = 3 から k = 8 までパターン P = "PAN" を配置した様子。この場合、k = 5 の位置で一致する。 文字列 S に対する操作を以下のように表す: S[i]: 文字列 S の i 番目の文字 S[i..j]: 文字列 S の i から j 番目までの部分文字列(i 文字目、j 文字目をそれぞれ含む) 文字列 S に含まれる文字の個数を文字列の長さと定義する。また、文字列 S の先頭を含む部分文字列をプレフィックス、末尾を含む部分文字列をサフィックスと定義する。 len(S):S の長さ S[1..i], 1 ≤ i ≤ len(S):S のプレフィックス S[i..len(S)], 1 ≤ i ≤ len(S):S のサフィックス 検索文字列をパターンと呼び、P で表す。被検索文字列をテキストと呼び、T で表す。また T