如何獲得可能的重疊匹配字符串

我正在尋找一種方式，無論是在Ruby或Javascript中，這將使我可以重疊，在一個字符串對正則表達式的所有匹配。如何獲得可能的重疊匹配字符串

比方說，我有str = "abcadc"，我想找到的a後跟任意數量的字符的出現，其次是c。我正在尋找的結果是["abc", "adc", "abcadc"]。任何想法如何我可以做到這一點？

str.scan(/a.*c/)會給我["abcadc"]，str.scan(/(?=(a.*c))/).flatten會給我["abcadc", "adc"]。

2016-01-23 wubbalubbadubdub

讀者：第一句話明確指出，所需要的是一個調用'all_matches（string，regex）'的方法，它可以處理任意字符串和正則表達式。 –

通常在使用正則表達式引擎時，匹配是「最長的」，除非你指定一個非貪婪的量詞，在那裏你得到「最左邊最短」的匹配。你無法真正期望在單一表達式中獲得最短和最長的時間。最短的時間，然後找到所有串聯排列將是最好的策略。 –

@theTinMan，原始問題指出，問題是關於給定正則表達式的匹配，這只是「讓我們說」一詞的一個例子。在你編輯之後，這個特定的正則表達式匹配看起來就像問題的要點。我不同意你的修改。 – ndn

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?"]

來源

2016-01-23 14:19:46 ndn

性能不如我的:) – mudasobwa

@mudasobwa，你的回答不是這個問題（又名給定的正則表達式，得到與之匹配的子串）。我的初始解決方案存在同樣的問題。 – ndn

我顯然沒有暈倒，但你的反對是愚蠢的：你提供的代碼，和我一樣，不只是一個神奇的正則表達式。這種情況下的神奇正則表達式並不存在，原因很明顯：用簡單的狀態機無法解決問題。 – mudasobwa

▶ 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字符邊界」，使得它與像'ábĉ'或'Üve Østergaard'字符串的工作

更多通用的解決方案，即接受任何‘從’和‘到’的序列，應該引進只是一個小的修改：找到的所有索引「FR om「和」to「。

來源

2016-01-23 14:22:54 mudasobwa

@ndn我不能，也謝謝你指出我不能「分裂（//）」。在''ábĉ''上試試。 – mudasobwa

假設OP的字符串和正則表達式只是一個例子，這並沒有給出一個通用的答案。 – ndn

在ruby 2中，您可以使用以下分割方法：'from = str.chars.to_a.map.with_index {| c，i |我如果c =='a'} .compact' –

在JS：

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>";

來源

2016-01-23 14:31:10

試試'ábĉ'。 – mudasobwa

@mudasobwa：它運行良好，因爲它會嘗試輸入字符串的所有可能的子字符串。 –

是的，運作良好，很好。 –

在Ruby中，你可以使用達到預期的結果：

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

無論這種方式對你的作品在很大程度上取決於你到底想要實現。

我試圖把它放到一個表達式中，但是我無法使它工作。我真的很想知道是否存在某些科學原因，這些原因不能用正則表達式解析，或者如果我對Ruby的解析器Oniguruma不夠了解。

來源

2016-01-23 14:35:16 aef

假設OP的字符串和正則表達式只是一個例子，這並沒有給出一個通用的答案。 – ndn

如果是這樣，請給出一個不起作用的例子。 – aef

如果問題是關於匹配'/ b。* d /'，那該怎麼辦？或者關於'/x.*y.*z。* [^ m] * foo /'？ – ndn

RegExp/(a.c)|(a.*c)/g的方法是匹配"a"字符後跟任何字符後跟"c"; "a.*c"匹配"a"後跟任何字符後跟前面的字符後跟"c"字符;注意RegExp在(a.*c)可能可以改善。在條件檢查if如果輸入字符串最後一個字符爲"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(" ")

來源

2016-01-23 15:07:48 guest271314

請解釋爲什麼這是有用的。建議代碼很好，但是解釋爲什麼代碼是正確的教育那些搜索解決方案的人，以便以後可以重用。 –

將*置於答案中*不在評論中。 –

@theTinMan查看更新後的帖子。 – guest271314

你想要所有可能的匹配，包括重疊的。正如您所指出的，「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); }); 
}

來源

2016-01-23 15:09:30

這裏有一個方法類似於@ 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"]

來源

2016-01-23 19:50:58

如何獲得可能的重疊匹配字符串

回答

相關問題