Java рекурсивное (?) Повторное (?) Глубокое (?) Сопоставление с образцом - PullRequest
Новая
       4

Java рекурсивное (?) Повторное (?) Глубокое (?) Сопоставление с образцом

5 голосов
/ 06 сентября 2011

Я пытаюсь получить ALL подстроки во входной строке, которые соответствуют заданному шаблону.

Например,

Заданная строка: aaxxbbaxb
Шаблон: a [a-z] {0,3} b
(На самом деле я хочу выразить следующее: все шаблоны, которые начинаются с a и заканчиваются на b, но могут содержать до 2 алфавитов между ними)

Точные результаты, которые я хочу (с их индексами):

aaxxb: индекс 0 ~ 4
axxb: индекс 1 ~ 4
axxbb: индекс 1 ~ 5
axb: индекс 6 ~ 8

Но когда я запускаю его через классы Pattern и Matcher, используя Pattern.compile() и Matcher.find(), он дает мне только:

aaxxb: индекс 0 ~ 4
axb: индекс 6 ~ 8

Это фрагмент кода, который я использовал. 

Pattern pattern = Pattern.compile("a[a-z]{0,3}b", Pattern.CASE_INSENSITIVE);
Matcher match = pattern.matcher("aaxxbbaxb");
while (match.find()) {
    System.out.println(match.group());
}

Как мне извлечь каждый фрагмент строки, соответствующий шаблону ?

Конечно, он не должен использовать классы Pattern и Matcher, если он эффективен:)

Ответы [ 3 ]

3 голосов
/ 05 июля 2012

(см .: Все перекрывающиеся подстроки, соответствующие регулярному выражению Java )

Вот полное решение, которое я придумал.Он может обрабатывать шаблоны нулевой ширины, границы и т. Д. В исходном регулярном выражении.Он просматривает все подстроки текстовой строки и проверяет, соответствует ли регулярное выражение только в определенной позиции, дополняя шаблон соответствующим количеством символов подстановки в начале и конце.Похоже, что это работает для случаев, которые я пытался - хотя я не сделал обширное тестирование.Это, безусловно, менее эффективно, чем могло бы быть. 

  public static void allMatches(String text, String regex)
  {
    for (int i = 0; i < text.length(); ++i) {
      for (int j = i + 1; j <= text.length(); ++j) {
        String positionSpecificPattern = "((?<=^.{"+i+"})("+regex+")(?=.{"+(text.length() - j)+"}$))";
        Matcher m = Pattern.compile(positionSpecificPattern).matcher(text);

        if (m.find()) 
        {   
          System.out.println("Match found: \"" + (m.group()) + "\" at position [" + i + ", " + j + ")");
        }   
      }   
    }   
  }
1 голос
/ 06 сентября 2011

вы фактически ищете строки ab, a_b и a__b во входной строке, где _ обозначает непробельный символ, значение которого вас не волнует.

Это три цели поиска. Наиболее эффективный способ сделать это - использовать алгоритм поиска, такой как алгоритм Кнута-Морриса-Пратта , с некоторыми изменениями. По сути, ваш псевдокод будет выглядеть примерно так: 

for i in 0 to sourcestring.length
    check sourcestring[i] - is it a? if so, check sourcestring[i+x] 
       // where x is the index of the search string - 1
    if matches then save i to output list
    else i = i + searchstring.length

очевидно, если у вас есть совпадение позиций, вы должны проверить внутренние символы подстроки, чтобы убедиться, что они в алфавитном порядке.

запустить алгоритм 3 раза, по одному для каждого поискового запроса. Несомненно, это будет намного быстрее, чем попытка поиска с использованием сопоставления с шаблоном.

edit - извините, неправильно прочитал вопрос. Если у вас есть для использования регулярных выражений, вышеприведенное не будет работать для вас.

0 голосов
/ 06 сентября 2011

Одна вещь, которую вы могли бы сделать:

  • Создайте все возможные подстроки длиной не более 4 символов (хорошо удачи с этим, если ваша строка большая)
  • Создать новый Matcher для каждой из этих подстрок
  • сделать поиск () вместо поиска ()
  • вычисление абсолютного смещения из относительного смещения подстроки и информации о совпадении
...