Исполнение вхождений подстроки в строку - PullRequest
Новая
       11

Исполнение вхождений подстроки в строку

0 голосов
/ 27 августа 2010

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

В демонстрационных целях я использовал строку «Кот сидел намат "и поиск всех вхождений подстроки" в ".В конечном итоге это должно привести к количеству совпадений 3. Так как я сейчас программирую на Java, первое, что пришло мне в голову, это: 

    public static void main(String[] args) {

      int count=0;
      String s = "The cat sat on the mat";

      Pattern pattern = Pattern.compile("at");
      Matcher matcher = pattern.matcher(s);
      while(matcher.find()){
          count++;
      }

      System.out.println("Pattern: "+pattern+" Count: "+count);
    }

Почему-то я сомневаюсь, что это оптимальное решениедля этой проблемы.Поэтому, если кто-то знает, как должно выглядеть оптимальное (или, по крайней мере, довольно хорошее) решение ... ответьте!Вы можете опубликовать свой ответ на любом языке, не обязательно Java (хотя это было бы здорово :)).

Большое спасибо!

Ответы [ 3 ]

2 голосов
/ 27 августа 2010

Есть довольно впечатляющие алгоритмы подстроки.Часто упоминается алгоритм Бойера-Мура (http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm), но есть и другие альтернативы, такие как http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm и http://en.wikipedia.org/wiki/Rabin-karp.

1 голос
/ 28 августа 2010

Без издержек на регулярные выражения: 

public static void main(String[] args) {

    int count = 0;
    String s = "The cat sat on the mat";
    String substring = "at";

    int pos = s.indexOf(substring);
    while (pos > -1) {
        count++;
        pos = s.indexOf(substring, pos + 1);
    }

    System.out.println("Pattern: "+pattern+" Count: "+count);
}

Я быстро проверил поиск «at» в тексте алгоритма поиска строки Бойера – Мура в Википедии. Они оба находят одинаковое количество совпадений, но выполнение этого на моей машине 10.000 раз потребовало алгоритма регулярного выражения 1702 миллисекунды, а это всего 192!

0 голосов
/ 27 августа 2010

Как обычно, это зависит.

Теоретически лучшим подходом, вероятно, является использование суффиксных деревьев - но они начинают понимать только для очень больших строк.Суффиксные массивы немного сложнее в использовании, но имеют смысл для небольших строк.IIRC, алгоритм дефлирования zlib использует массивы суффиксов для поиска повторяющихся подстрок.В любом случае, алгоритмы не просты, и им нужно немного изучить, чтобы понять и эффективно реализовать.

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

...