Perl Regular Expression Matching is NP-Hard
Matching ordinary regular expresions can be done in polynomial time, proportional to MN, where M is the length of the regular expression and N is the length of the string to be matched. The usual method for this is: Parse the regular expression and construct an equivalent finite automaton (FA), which will have O(M) states; then simulate the action of the FA on the input, which takes O(MN) time. My
後方参照のある正規表現の能力 - まめめも
定期的に出てくる話題ですが、プログラミングで出てくる正規表現は正規表現ではないので、素数判定ができます。正確には、文字列の長さが素数かどうかを判定できます。2 文字以上のマッチが 2 回以上出現するかどうかを見ます。後方参照がポイント。 p (2..30).select{|x| !("X" * x)[/^(..+)\1+$/] } #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] ところで、{ a^n | n は素数 } は文脈依存言語のはずなので、後方参照のある正規表現は線形拘束オートマトン以上の表現力を持つことになるのでしょうか。でも、文脈自由文法である { a^nb^n | n は自然数 } や括弧の対応は書けなさそうです。ちょっと調べてみても、後方参照のある正規表現の能力はよくわかりませんでした。 とりあえずPerl の正規表現マッチングで 3-CN
範囲演算子 - ぱるも日記
スライスを勉強した時に「範囲構文」として勉強した「a..b」という書き方ですが、ラクダ本を読んでいたところ、これは構文というよりは「..」という「範囲演算子」によるもの、という事がわかりました。 今まで「整数と整数の間の範囲の整数リストを作り出す」という程度の認識で使っていたのですが、やはりちゃんと勉強しないとダメですね。知らなかった使い方が見つかりました。(^_^;) というわけで、範囲演算子をちゃんと勉強したいと思います。 ラクダ本（プログラミングPerl〈VOLUME1〉）によると、範囲演算子（range operator）は「コンテキスト」によってその意味が変わるそうです。 「コンテキスト」は、ぱるも日記でも何度か登場して勉強していますが、「文脈」の事ですね。スカラー変数への代入文の右辺や if 文の条件文など、「スカラー値」が必要と判断される場所は「スカラーコンテキスト」と呼ばれ
japan.linux.com | GD::Graphを使ったPerlグラフ生成
PerlのGD::Graphモジュールは、データをすばやく簡単にグラフィカルに表現するためのソフトウェア開発者向けツールだ。もともとはMartien Verbruggenが1995年に作成したこのパッケージは、非常に柔軟で人気の高いツールへと成長した。データベースなどから動的データセットを即座に取得して表示したいという場合に好適である。企業のイントラネットで広く使われており、まさに経営陣が望むような形式でデータを示すグラフを生成できるので、多くのWeb管理者が利用している。 GD::Graphは、下位レベルのユーティリティモジュール集合の上に成り立っている。これらのモジュールの最も基礎的な部分は、Thomas BoutellのGDグラフィックスプリミティブライブラリであり、各種の、線、多角形、テキストをメモリ内カンバスに描画する構造を提供する。このライブラリの上に、2つのPerlモジュー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
『dfltweb1.onamae.com – このドメインはお名前.comで取得されています。』へのコメント
Junya Kondo / Text-Hatena-0.20 - search.cpan.org
