ストーリー

こんにちは、25Bのくあらんてぃんです。

traPの部内SNSであるtraQには、いわゆるエゴサツールとしてtraQ gazerという内製サービスが広く使われています。登録した単語が含まれる投稿を通知してくれるbotで、正規表現を用いることもできる優れものです。

2023 春ハッカソン 15班 「traQ gazer」

2023年春に開催されたハッカソンで「traQ gazer」を開発しました。traPでは部内SNSとして、内製の「traQ」が利用されています。このtraQは500人を超える部員に利用されており、日々多くの投稿がされます。traQ gazerは、そんなtraQを円滑に利用するためのツール

東京科学大学デジタル創作同好会traPoribe

traQユーザーたちは自身のユーザー名やその他呼称をgazerに登録することで、知らないところでの言及を見逃さないようにしています。

くあらんてぃんの e は10文字なのですが、それにちなんで僕に関する事柄を {任意の文字}*10 を含めて表現することがあるらしいです。(略しすぎでは？)
これらを検知できるような正規表現をgazerに登録したいと考えました。

(はやく答えを知りたい人はこちら)

問題文

いくつかの行からなる文字列 $S$ が与えられます。 $S$ の連続する部分文字列の中に、以下の条件を満たすものが存在するかを判定する正規表現を作成してください。

• 部分文字列に含まれる文字は全て同一である
• 以上を満たすような部分文字列の中で極大である
• 部分文字列の長さはちょうど $10$ である

より厳密には、長さ $L$ の文字列について、

• $0\le i<j\le L$
• $S_i=S_{i+1}=\cdots =S_{j-1}$
• $i=0$ または $S_{i-1}\ne S_i$
• $j=L$ または $S_{j-1}\ne S_j$

が成り立つような $(i,j)$ の組が存在するかを判定する正規表現を作成してください。

制約

正規表現は /  に挟まれている必要がある (例：/tra(P|Q)er/)

正規表現の長さは / を含めて 50 以下 (traQ gazerの制約)

$L\le 10^4$ (traQの制約)

正規表現はMySQLの実装を用いる。(おそらくICUを用いて実装されているはず？)

入力例

(簡単のため、各行について判定する例を示す)

quarantineeeeeeeeee
waaaaaaaaaai
oyooooooooo
quaaaaaaaaaaaran
oooooooooo_o

出力例

true
true
false
false
true

解答

/(?<=^|(.))(?!\1)(.)\2{9}(?!\2)/

{9} の部分を変えることで他の文字数の連続でも対応できます。
10連続の改行とかにはマッチしないかもしれないけど見逃してください。

解説

こういうことです。

/(?<=^|(.))(?!\1)(.)\2{9}(?!\2)/
  ^^^^^^^^  ^^^^ ^^^^^^^^ ^^^^
     │       │     │      └─ 後ろに\2はない
     │       │     └─ 任意の文字が10連続
     │       └─ 後ろに\1はない
     └─ 前に文頭または1文字

詳しい説明

ここからは正規表現を考えついた手順と詳しい説明を載せます。

まず、同じ文字の繰り返しは以下のように表せます。

/e{10}/
 ^^^^^
   └─ e が10文字連続する

キャプチャグループは、() で囲んだ部分にマッチした文字列を、その後の後方参照 (\1 みたいなやつ) で使えます。

/(.)\1{9}/
 ^^^^^^^^
    └─ 任意の文字が10文字連続する

最初の (.) が任意の1文字にマッチして、それに続く \1{9} はその1文字の9回繰り返しを意味します。

10文字の連続後は同じ文字が続いてほしくありません。否定を表す方法として文字クラス [^ ...] がありますが、文字クラスには後方参照を含められないらしいです。そのため、別の方法として、否定先読み (?! ...) を使います。

/(.)\1{9}(?!\1)/
         ^^^^^^
           └─ 後ろには同じ文字が来ない

文字列の後ろ側を見ることを先読みというため、なんとなく混乱してしまうことがあるかもしれません。正規表現エンジンは文字列の文頭から文末に向かって位置を進めていくということを考えると、文末側を見るのが先読み(ahead)で、文頭側を見るのが後読み(behind)であることも腑に落ちると思います。

しかしこのままでは、11文字以上連続していたとしても、途中からマッチしてしまいます。

quaaaaaaaaaaaran
   ~~~~~~~~~~^
        └─ ｱｯﾀ!!!

文頭側にも異なる文字が存在することを確認したいです。
否定後読みを使うとよさそうですが、以下のようにしてもうまくいきません。

/(?<!\1)(.)\1{9}(?!\1)/

\1 が定まる前に後方参照の判定が行われてしまっているのが原因です。この場合、後方参照には何も入ってないため、nullのような状態として処理されるらしいです。実装によってはエラーになることもありそうです。(後方参照という名前からも想像がつきますね)

そこで視点を変えて、前の1文字から見て、次の1文字が異なることを確認すればよいということを思いつきます。先読みはパターン中のどこでも使えるので、以下のようにします。

/(.)(?!\1)(.)\2{9}(?!\2)/
  ^ ^^^^^^
  │   └─ 後ろは同じ文字ではない
  └─ 任意の1文字が存在

いい感じになってきました。
今のままだと、文頭に10連続が存在したときにはマッチしてくれません。文頭の記号 ^ を使うことで対応できるようにします。

/(^|(.)(?!\2))(.)\3{9}(?!\3)/
  ^^^^^^^^^^^
    └─ 文頭 または 任意の1文字で後ろが異なる

「または」の範囲を正しく指定するために括弧を使ったため、後方参照のナンバリングがずれています。非キャプチャグループ (?: ...) を用いると、ナンバリングをずらさずに表すことができます。

/(?:^|(.)(?!\1))(.)\2{9}(?!\2)/

ちなみに、以下のように書くこともできます。

/(?:^|(.))(?!\1)(.)\2{9}(?!\2)/
    ^^^^^ ^^^^^^
      │    └─ 後ろが\1と異なる
      └─ 文頭または任意の1文字

最初の括弧で文頭にマッチした場合は \1 がnullになり、否定先読みは常に成功します。

存在の判定のみならこれで完成です。ただ、このままでは1つ手前の文字までマッチに含まれているため、マッチした範囲を用いて置換などの操作をする場合は不便です。

quarantineeeeeeeeee
        ~~~~~~~~~~~
             └─ ｱｯﾀﾖ!!

判定に使いたいけどマッチに含めたくない場合は、後読みを使うとうまくいきます。

/(?<=^|(.))(?!\1)(.)\2{9}(?!\2)/

waaaaaaaaaai
^~~~~~~~~~~^
     └─ ﾜｰｲ!!!

regex101 などのサイトを使うと、実際にちょうど10文字の連続だけにマッチしていることが確かめられます。このサイトは他にも、正規表現のデバッグやベンチマークなどもできるので是非遊んでみてください。(正規表現の説明もできます。この記事の存在意義が……)

regex101: build, test, and debug regex

Regular expression tester with syntax highlighting, explanation, cheat sheet for PHP/PCRE, Python, GO, JavaScript, Java, C#/.NET, Rust.

regex101Firas Dib

ちなみに、先読みや後読みと呼ばれる記法の類は、ゼロ幅アサーションとも呼ばれます。マッチ結果に影響させずに条件だけ追加したいときに使う、と覚えておくとよさそうです。個人的には全然覚えられなかった記法なのですが、並べて書いてみると規則性を掴みやすいです。

? は高度な記法のための接頭辞のような役割と考えるとわかりやすいです。(? と ) で挟む記法は他にも多く存在するので、気になった方はICUのドキュメントなどを見てみるといいかもしれません。

おわりに

比較的構成するのが難しいかも？と感じたのでブログに書いてみました。

traQ gazerに設定してみると、世の中には僕と無関係なちょうど10文字の連続が意外と多く存在することに気付かされます。

プログラムを書ける場合はまず正規表現で行う操作ではない気がしますが、組版言語で競プロしてる方々と比較したら圧倒的にマシでしょう。

明日の投稿者は@SyntaxError、@otimaです。皆さんもよい正規表現ライフを！