Regex, чтобы найти все подстроки и самую длинную подстроку

Question

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

Я хочу сделать следующее: Учитывая поисковую строку :

Сиэтл потрясающий

Я хочу найти все его подстроки в данном предложении.Поэтому применение регулярного выражения в следующем предложении

Сиэтл - это потрясающе, это потрясающе - это потрясающе - это Сиэтл

Должно дать мне

Сиэтл, Сиэтл - это здорово, это здорово, это - Сиэтл

Одно ограничение, которое может быть полезным, состоит в том, что в предложении всегда будут присутствовать только слова, присутствующие в строке поиска.и пробелы между ними.

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

удивительный Сиэтл

в приведенном выше предложении дает нам

удивительный, Сиэтл и

Я не уверен, что что-то подобное можно сделать с помощью регулярного выражения, так как оно жадное.Был бы признателен за понимание этого!Я знаком с C # и Java и могу использовать любую из их библиотек регулярных выражений.

Answer 1

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

Answer 2

Нет хорошего способа выразить такой шаблон непосредственно с помощью регулярного выражения.

Вам необходимо перечислить все разрешенные комбинации:

Seattle is awesome|Seattle is|Seattle|is awesome|is|awesome

или более кратко:

Seattle( is( awesome)?)?|is( awesome)?|awesome

Вы можете программно преобразовать вашу входную строку в этот формат.

Answer 3

В Java не проверено . Это возвращает итератор в списках строк. Каждый список является соответствующей подпоследовательностью. Просто поместите пробелы между членами списка для печати. Если это привыкнет много , использование intern () может быть плохим.

static Iterator<List<String>> getSequences(String squery, String starget)
{
    List<String> query = Arrays.asList(squery.split(" "));
    for ( int i = 0; i < query.size(); i++)
        query.set(i, query.get(i).intern());
    List<String> target = Arrays.asList(starget.split(" "));;
    for ( int i = 0; i < target.size(); i++)
        target.set(i, target.get(i).intern());

    // Because the strings are all intern'ed, this HashSet acts like we want -
    // If two lists are the same sequence of words, they are equal.
    // It's used to remove duplicates.
    HashSet<List<String>> ret = new HashSet<List<String>>();
    for ( int qBegin = 0; qBegin < query.size(); qBegin++ )     {
        for ( int tBegin = 0; tBegin < target.size(); tBegin++ ) {
            for ( int iCursor = 0; 
                  iCursor < min(query.size()-qBegin, target.size()- tBegin); 
                  iCursor++)                {
                if ( query.get(qBegin+iCursor)==target.get(tBegin+iCursor) )
                    ret.add(query.subList(qBegin, qBegin+iCursor+1));
                else break;
            }
        }
    }
    return ret.iterator();
}

static int min(int a, int b) { return (a<b)? a:b; }

Answer 4

Можете ли вы описать вашу проблему немного дальше? Это больше похоже на поисковую систему, чем на простое сопоставление строк. Я очень рекомендую проверить Apache Lucene - у него есть некоторая кривая обучения, но это отличный маленький инструмент для интеллектуального поиска. Он обрабатывает множество вещей, которые попадают в ловушку при работе с поиском. Вы можете настроить оценку попаданий так, чтобы в точности соответствовать тому, что вы описываете.