• (文字列1|文字列2|...)の形のパタンの認識
• KMP法の拡張
  • 失敗関数を使用(KMP法よりも複雑)
• fgrepコマンドで使用
• 例: ac|baa|bacd|ba|bbの認識