パソコン詳しくない系競プロ勢向け正規表現 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

この記事は「競プロ!!」競技プログラミング Advent Calendar 2017の記事として書かれたものです。
上のリンク先にはリンクが張られていないので書いておきますが、競プロadvent calendarはもう１つあります。
昨日の記事 / 明日の記事（明日の記事がすでにあるのなーんでだ？）

はじめに
正規表現入門
競プロで正規表現を使う
- C++での使い方
- 応用例
正規表現で入力チェッカを書く

はじめに

とりあえずカレンダーに登録してからネタを考えていたのですが、そういえば正規表現って使ったことない人結構いるよなぁと思ったので軽く紹介します。
正規表現、かなり強力なツールなので使えるようになる価値は大いにあると思います。
入力チェッカを書くときとか重宝しているので布教しておきます。

正規表現入門

正規表現とは、文字列の集合を一つの文字列で表現する方法の一つである。(wikipediaより)
強そう。
まずは例からみてみましょう。

例：にゃーん

nyaa*nという正現表規を考えます。
正規表現において '*' は「直前のものを0回以上繰り返す」という意味です。
つまりこの正規表現には "nyan"、"nyaan"、"nyaaaaaan" のような文字列がマッチします。

なにが嬉しいのか

正規表現を使うと主に以下のことができます。

ある文字列が、あるパターンに当てはまっているかをチェックする(match)
ある文字列から、あるパターンに当てはまる部分を取り出す(find)

上は競プロのYES/NO問題とか、入力チェッカとかに使ってます。
下は簡易的なスクレイピングとか文書からなんらかの情報を取り出したりだとか一斉置換（例えば「"~~~"」を「'~~~'」に一斉置換したいとき）とか、色々使ってます。
この記事では下は扱いませんが、興味が湧いたら使い方を調べて使ってみてください。

よく使う機能一覧

正規表現には '*' の他にも様々な特殊文字が用意されています。
そのうち僕が特によく使うものの一覧を書いておきます。
「例」のリンク先には正規表現の例とテストケースが書かれていて、Match resultで青くなっている行のみがその正規表現にマッチすることを表しています。

文字	意味	備考
`^`	行頭	例
`$`	行末	例
`*`	直前のものを0回以上繰り返す	例
`+`	直前のものを1回以上繰り返す	つまり上の例は`nya+n`とも書けます
`?`	直前のものを0回または1回繰り返す	例
`{n}`	直前のものをちょうどn回繰り返す	例
`{n,m}`	直前のものをn回以上m回以下繰り返す	例
`{n,}`	直前のものをn回以上繰り返す	例
`(〜)`	括弧内をひとまとめにできる感じ	例
`｜`	または	例
`.`	任意の文字にマッチする	例 `.*`で任意の文字列を表せる
`[〜]`	括弧内のいずれかの文字にマッチする	例
`[a-z]`	a-zのどれかにマッチする	例
`[^〜]`	括弧内以外の文字にマッチする	例
`\d`	数字(0-9)にマッチする	例
`\w`	`[A-Za-z0-9_]`と同じ
`\s`	空白（スペース/タブ/改行）にマッチする	例

まだまだ便利な機能があるので興味が湧いたら適当に調べてみてください。

競プロで正規表現を使う

C++での使い方

C++11からstd::regexが追加されたのでそれを使います。
以下は入力された文字列が"にゃーん"かどうかを判定するプログラムです。

#include <regex>
#include <iostream>
using namespace std;

int main() {
  regex re("nya+n");
  string s;
  while (cin >> s) {
    bool res = regex_match(s, re);
    cout << (res?"YES":"NO") << endl;
  }
  return 0;
}

ideone

regexのコンストラクタでは正規表現をコンパイルしていて重いので何度もマッチングする場合はこのようにコンストラクタを１回しか呼ばないように書いた方がいいでしょう。

応用例

CODE FESTIVAL 2017 A - AKIBA
場合分けをとかをするとWAを出しがちなのであらかじめ全列挙しておいてチェックするみたいなのが想定解でしたが、正規表現を使うとあっさり解けて嬉しいということに後で気づきました。

#include <regex>
#include <iostream>
using namespace std;

int main() {
  regex re("A?KIHA?BA?RA?");
  string s;
  cin >> s;
  bool res = regex_match(s, re);
  cout << (res?"YES":"NO") << endl;
  return 0;
}

あとは、この問題を意識して作ったこの問題もどうぞ。（解説記事）
動的に正規表現を組み立てると解ける問題です。
ただこういうことをする場合は、C++の正規表現は実用面ではともかく競プロ的には微妙な実装なので、D言語などを使うと良いでしょう。

他の応用例はyurahunaさんの記事に載っているので是非お読みください。

まぁでも基本的には競プロそのものに使う場合は少し楽になる程度の嬉しさしかないケースが大半かもしれません。

正規表現で入力チェッカを書く

僕は最近はずっとwriter/testerをするときは正規表現を使って入力チェックをしていて、かなり快適なのでオススメしておきます。

以下は僕が使ってるコードです。

#! /usr/bin/python
import re, sys, os

re_num = '(0|-?[1-9]\d*)' # 整数の正規表現（負数/0にも対応）

def check(fname, f):
  lines = re.split(r'\r*\n',f.read()) # windowsの改行コードにも対応
  global li; li = 0
  def get(): # 次の行を取得
    global li
    in_s = lines[li]; li += 1
    return in_s
  def getf(fmt): # 正規表現チェック付きで次の行を取得
    in_s = get()
    assert re.match('^%s$'%fmt, in_s), 'format : line {}'.format(li)
    return in_s
  def geti(): # 次の行を整数１個として取得
    return int(getf(re_num))
  def getis(n): # 次の行を整数 n 個として取得
    return list(map(int, getf('{0}( {0}){{{1}}}'.format(re_num,n-1)).split()))
  def getil(*l): # 次の行を整数 hoge 個として範囲制約付きで取得（引数には長さ２のリストをhoge個渡す）
    if isinstance(l[0], int):
      val = int(getf(re_num))
      assert l[0] <= val <= l[1], 'out of range : line {}'.format(li)
      return val
    vals = getis(len(l))
    for nx,nl in zip(vals,l):
      assert nl[0] <= nx <= nl[1], 'out of range : line {}'.format(li)
    return vals
  def getils(l,r,n): # 次の行を l 以上 r 以下の整数 n 個として取得
    return getil(*[[l,r]]*n)
  def eof(): # EOFチェック
    assert lines[li:] == [''], 'EOF'

  MN = 10**5
  MX = 10**9

  n = getil(1,MN) # 1 以上 MN 以下の整数を読み込む（１個だけのときは(下限,上限)を引数として渡す）
  a, b = getil([1,MX], [1,MX]) # 1 以上 MX 以下の整数を２つ読み込む（getils(1,MX,2)とも書ける）
  eof()

  print('o')


if __name__ == '__main__':
  for fname in sorted(os.listdir('../in/')): # 
    if fname[0] == '.': continue
    sys.stdout.write(fname + ': ')
    with open('../in/' + fname) as f:
      try:
        check(fname, f)
      except AssertionError as e:
        print('invalid! ({})'.format(e))

コメントなしバージョンもgistに上げておきます。
C++でも例えば「Sは小文字アルファベットのみからなる長さ10以下の文字列である」を "[a-z]{1,10}" みたいに正規表現でチェックしたりするだけでもいい感じだと思います。
testlib.hを使っている人は、たしかtestlib自体にそういう機能があったはずなのでそれを使うといいかもです。（testlib.h内で"regex"で検索かけるとそれっぽいところが見つかるはず）

おまけ：{}とか使うとやばい正規表現が作れるんですね。
Ideone.com - 5f3WAn - Online Go Compiler & Debugging Tool
Ideone.com - Glf1Wl - Online C++0x Compiler & Debugging Tool