Как получить совпадающие совпадения в строке

Ответ 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?"]

Ответ 2

В Ruby вы можете достичь ожидаемого результата, используя:

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

Работает ли этот способ для вас в значительной степени зависит от того, чего вы действительно хотите достичь.

Я попытался поместить это в одно выражение, но я не смог заставить его работать. Мне бы очень хотелось узнать, есть ли какая-то научная причина, которую невозможно проанализировать с помощью регулярных выражений, или если я просто не знаю достаточно о Ruby parser Oniguruma, чтобы сделать это.

Ответ 3

Вы хотите все возможные совпадения, включая перекрывающиеся. Как вы уже заметили, трюк с "Как найти совпадающие совпадения с регулярным выражением?" не работает для вашего случая.

Единственное, что я могу думать об этом, будет работать в общем случае - это сгенерировать все возможные подстроки строки и проверить каждый из них на привязанной версии регулярного выражения. Это грубая сила, но она работает.

Ruby:

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); });
}

Ответ 4

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

Ответ 5

▶ 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 char border" позволяет работать со строками типа 'ábĉ' или 'Üve Østergaard'.

Для более общего решения, которое принимает любые последовательности "от" и "до", нужно внести лишь небольшую модификацию: найти все индексы "от" и "до" в строке.

Ответ 6

Здесь используется подход, похожий на @ndn и @Mark, который работает с любой строкой и регулярным выражением. Я реализовал это как метод 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"] 

Ответ 7

Подход 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(" ")

Ответ 8

Этот подход JavaScript предлагает преимущество перед ответом Wiktor, лениво итерируя подстроки данной строки, используя функцию генератора, которая позволяет вам использовать одно совпадение за раз для входных строк очень больших строк, используя цикл for...of чем генерирование целого массива совпадений одновременно, что может привести к исключениям нехватки памяти, так как количество подстрок для строки растет квадратично с длиной:

function * substrings (str) {
  for (let length = 1; length <= str.length; length++) {
    for (let i = 0; i <= str.length - length; i++) {
      yield str.slice(i, i + length);
    }
  }
}

function * matchSubstrings (str, re) {
  const subre = new RegExp('^${re.source}$', re.flags);
  
  for (const substr of substrings(str)) {
    if (subre.test(substr)) yield substr;
  }
}

for (const match of matchSubstrings('abcabc', /a.*c/)) {
  console.log(match);
}