文字列内で一致する可能性のある一致を得る方法

Question

RubyまたはJavascriptのいずれかで、正規表現に対して文字列内ですべての一致が重複する可能性がある方法を探しています。

---

のは、私がstr = "abcadc"を持っている、と私はcに続く任意の数の文字が続くaの出現を、見つけたいとしましょう。探しているのは["abc", "adc", "abcadc"]です。どのように私はこれを達成することができます上の任意のアイデア？

str.scan(/a.*c/)は、私には["abcadc"]、str.scan(/(?=(a.*c))/).flattenは私に["abcadc", "adc"]を与える。

Answer 1

def matching_substrings(string, regex) 
    string.size.times.each_with_object([]) do |start_index, maching_substrings| 
    start_index.upto(string.size.pred) do |end_index| 
     substring = string[start_index..end_index] 
     maching_substrings.push(substring) if substring =~ /^#{regex}$/ 
    end 
    end 
end 

matching_substrings('abcadc', /a.*c/) # => ["abc", "abcadc", "adc"] 
matching_substrings('foobarfoo', /(\w+).*\1/) 
    # => ["foobarf", 
    #  "foobarfo", 
    #  "foobarfoo", 
    #  "oo", 
    #  "oobarfo", 
    #  "oobarfoo", 
    #  "obarfo", 
    #  "obarfoo", 
    #  "oo"] 
matching_substrings('why is this downvoted?', /why.*/) 
    # => ["why", 
    #  "why ", 
    #  "why i", 
    #  "why is", 
    #  "why is ", 
    #  "why is t", 
    #  "why is th", 
    #  "why is thi", 
    #  "why is this", 
    #  "why is this ", 
    #  "why is this d", 
    #  "why is this do", 
    #  "why is this dow", 
    #  "why is this down", 
    #  "why is this downv", 
    #  "why is this downvo", 
    #  "why is this downvot", 
    #  "why is this downvote", 
    #  "why is this downvoted", 
    #  "why is this downvoted?"] 

Answer 2

▶ str = "abcadc" 
▶ from = str.split(/(?=\p{L})/).map.with_index { |c, i| i if c == 'a' }.compact 
▶ to = str.split(/(?=\p{L})/).map.with_index { |c, i| i if c == 'c' }.compact 
▶ from.product(to).select { |f,t| f < t }.map { |f,t| str[f..t] } 
#⇒ [ 
# [0] "abc", 
# [1] "abcadc", 
# [2] "adc" 
# ] 

私は、文字列内の文字のすべてのインデックスを見つけるための派手な方法があることを、信じて、私はそれを見つけることができませんでした:( 任意のアイデア？

分割「にUnicodeの文字の境界は、」それは'ábĉ'または'Üve Østergaard'のような文字列で動作するようになります

任意の受け入れ、より汎用的な解決策については、 『から』と 『に』配列を、一つはほんの少しの変更を導入する必要がありますのすべてのインデックスを見つける「FRを文字列に "om"と "to"を追加します。 JSで

Answer 3

：Rubyで

function doit(r, s) { 
 
    var res = [], cur; 
 
    r = RegExp('^(?:' + r.source + ')$', r.toString().replace(/^[\s\S]*\/(\w*)$/, '$1')); 
 
    r.global = false; 
 
    for (var q = 0; q < s.length; ++q) 
 
    for (var w = q; w <= s.length; ++w) 
 
     if (r.test(cur = s.substring(q, w))) 
 
     res.push(cur); 
 
    return res; 
 
} 
 
document.body.innerHTML += "<pre>" + JSON.stringify(doit(/a.*c/g, 'abcadc'), 0, 4) + "</pre>";

Answer 4

あなたが使用して期待どおりの結果を達成できます。この方法は、あなたのために働くかどうか

str = "abcadc" 
[/(a[^c]*c)/, /(a.*c)/].flat_map{ |pattern| str.scan(pattern) }.reduce(:+) 
# => ["abc", "adc", "abcadc"] 

は本当に何に大きく依存しています達成したい。

私はこれを単一の式に入れようとしましたが、動作させることができませんでした。正規表現では解析できない科学的な理由があるのか​​、それともRubyのパーサーOnigurumaには分かりませんか？

Answer 5

のアプローチRegExp/(a.c)|(a.*c)/gは、"a"文字に続いて任意の文字とそれに続く"c"と一致させます。 "a.*c"は"a"と一致し、任意の文字の後に先行する文字が続き、その後に"c"文字が続きます。 の注釈RegExpはおそらく改善される可能性があります。入力文字列の最後の文字が"c"であれば、true場合、あなたは重複も含め、すべての可能な一致が、欲しいres結果配列

var str = "abcadc" 
 
, res = str.match(/(a.c)|(a.*c)/g); 
 
if (str[str.length - 1] === "c") res.push(str); 
 

 
document.body.textContent = res.join(" ")

Answer 6

に完全な入力文字列をifチェックで条件を押してください。あなたが指摘したように、 "How to find overlapping matches with a regexp?"の先読みトリックはあなたのケースでは機能しません。

私が考えることができる一般的なケースでは、文字列の可能な部分文字列をすべて生成し、正規表現の固定されたバージョンに対してそれぞれをチェックすることしか考えられません。これはブルートフォースですが、機能します。

ルビー：

def all_matches(str, regex) 
    (n = str.length).times.reduce([]) do |subs, i| 
    subs += [*i..n].map { |j| str[i,j-i] } 
    end.uniq.grep /^#{regex}$/ 
end 

all_matches("abcadc", /a.*c/) 
#=> ["abc", "abcadc", "adc"] 

Javascriptを：

function allMatches(str, regex) { 
    var i, j, len = str.length, subs={}; 
    var anchored = new RegExp('^' + regex.source + '$'); 
    for (i=0; i<len; ++i) { 
    for (j=i; j<=len; ++j) { 
     subs[str.slice(i,j)] = true; 
    } 
    } 
    return Object.keys(subs).filter(function(s) { return s.match(anchored); }); 
} 

Answer 7

ここで任意の文字列と正規表現で動作する@ NDNのとマルコ@に似ているアプローチがあります。私はStringの方法としてこれを実装しました。なぜなら、それは私がそれを見たいと思うからです。 String#[]とString#scanに大きな賛辞はありませんか？

class String 
    def all_matches(regex) 
    return [] if empty? 
    r = /^#{regex}$/ 
    1.upto(size).with_object([]) { |i,a| 
     a.concat(each_char.each_cons(i).map(&:join).select { |s| s =~ r }) } 
    end 
end 

'abcadc'.all_matches /a.*c/ 
    # => ["abc", "abcadc", "adc"] 
'aaabaaa'.all_matches(/a.*a/) 
    #=> ["aa", "aa", "aa", "aa", "aaa", "aba", "aaa", "aaba", "abaa", "aaaba", 
    # "aabaa", "abaaa", "aaabaa", "aabaaa", "aaabaaa"]