Namaran

Code daily. Without assist.

2026-10-30

slug.cpp

#include <iostream>
#include <regex>
#include <string>

bool is_slug(const std::string& s) {
    static const std::regex re("[a-z]+(-?[a-z]+)*");
    return std::regex_match(s, re);
}

int main() {
    std::cout << is_slug("daily-code-drill") << '\n';
    std::cout << is_slug("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!") << '\n';
}

is_slug は、英小文字だけの語を - 1つでつないだ文字列(daily-code-drill など)かどうかを判定するつもりの関数です。main の1つ目の呼び出しはすぐに終わりますが、a を30個並べて ! で終わる文字列を渡す2つ目の呼び出しは戻ってこず、20秒待っても何も出力されませんでした。本来は 1 と 0 の2行がすぐに出力されるはずです。

Answer

Wrong

static const std::regex re("[a-z]+(-?[a-z]+)*");

-? は省略できるので、(-?[a-z]+) はハイフンの無い文字の並びにも合います。すると a が続く部分は、[a-z]+ と繰り返しの各回にどう分けても合い、30個の a の間にある29か所それぞれで「ここで区切るか」を選べるので、分け方は2の29乗、約5億通りあります。一致する文字列なら、最初に試した分け方がそのまま成功するので、1つ目の呼び出しはすぐに終わります。

2つ目の文字列は最後の ! にどの分け方でも合いません。std::regex は分け方を1つずつ試し、失敗すると1つ前の選択に戻って別の分け方を試すので、一致しないと言えるのは約5億通りをすべて試し終えたときです。a が1つ増えるたびに分け方は2倍になり、手元では a が26個で30秒を超えました。

Right

static const std::regex re("[a-z]+(-[a-z]+)*");

繰り返しの各回を - で始めると、区切りを置けるのはハイフンの位置だけになり、文字列の分け方は1通りに決まります。一致しない文字列でも試す分け方が増えないので、すぐに失敗が分かります。ハイフンの無い1語は先頭の [a-z]+ がすでに受け持っているので、? を外しても、一致する文字列の範囲は変わりません1。

  1. 一致しない入力で照合の時間が爆発する正規表現は、外から長い入力を送るだけでサーバーを止められるので、ReDoS(正規表現によるサービス妨害)と呼ばれます。2016年には Stack Overflow が、行頭と行末の空白を取り除く正規表現に空白が約2万個続く投稿を渡し、約34分止まりました。こちらは時間が入力の長さの2乗で増える例で、この問題ほど急ではありませんが、原因は同じく、失敗が確定するまで試す位置が多すぎることでした。