Как удалить подстроку максимальной длины, начинающуюся и заканчивающуюся заданными символами?

#java #строки #подстрока

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

Итак, есть String sentence;. Надо удалить подстроку из слова, начинающуюся и заканчивающуюся
заданными символами, например, "а" и "б". Удалить только в слове с максимальной длиной
подстроки. 

Сам я разбил предложение на слова в цикле, искал слова, которые содержат "а" и "б"
и выбирал из них самое длинное, где и удалял подстроку. Однако, слово может быть длиннее,
а подстрока короче. 

Как это сделать лучше? 

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

Ответы

Ответ 1

Для простоты задачи предположним, что слова разделены только пробельными символами
(имеются ввиду любые пробелы в Unicode).

import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class HelloWorld
{
  public static void main(String[] args)
  {
    String text = "а+б а++б +а+++б+ ++а++++б++";

    // паттерн означает строку, которая содержит один или более непробельных символов
"\\S+"
    // перед которыми подстрока "а" (франгмент (?<=а) — это так называемый positive
lookbehind),
    // после которых подстрока "б" (франгмент (?=б) — это так называемый positive
lookahead).
    String regexPattern = "(?<=а)\\S+(?=б)";

    // получаем объект для итерации по всем совпадениям
    Matcher matcher = Pattern.compile(regexPattern).matcher(text);

    // для хранения максимульной длины совпадения
    int maxLength = 0;
    // для хранения индексов самого длинного совпадения
    int startIndex = -1;
    int endIndex = -1;

    // итерируемся по всем совпадениям
    while (matcher.find()) {

      int length = matcher.end() - matcher.start();
      // если совпадение самое длинное, то сохраняем его индексы
      if (length > maxLength) {
        startIndex = matcher.start();
        endIndex = matcher.end();
      }
    }

    // если совпадение найдено (оно будет самым длинным), то вырезаем его
    if (startIndex > 0)
      text = text.substring(0, startIndex) + text.substring(endIndex);

    System.out.println(text);
  }
}


Ответ 2

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

string RemoveSubString(string str, char start, char end)
{
    int s = -1;
    int e = -1;     
    int pointer = 0;

    while(pointer < str.Length)
    {   
        while(pointer < str.Length && str[pointer]!=start && str[pointer]!=' ') pointer++;  

        if (pointer < str.Length && str[pointer]==start)
        {           
            int s1 = pointer;           
            pointer++;
            while(pointer < str.Length && str[pointer]!=end && str[pointer]!=' ')
pointer++;

            if (pointer < str.Length && str[pointer] == end)
            {
                int e1 = pointer;               

                if(s == -1 || (e-s) < (e1-s1))
                {
                    s=s1;
                    e=e1;
                }                               
            }   else pointer++;     
        } else pointer++;
    }   

    if ((e-s) < 2) return str;  
    return str.Substring(0, s+1) + str.Substring(e, str.Length-e);
}


Проверка

Console.WriteLine(RemoveSubString("а+б а++б +а+++б+ ++а++++б++", 'а', 'б'));
Console.WriteLine(RemoveSubString("а+б_а++б_+а+++б+_++а++++б++", 'а', 'б'));
Console.WriteLine(RemoveSubString("1-----2-------2--------2", '1', '2'));
Console.WriteLine(RemoveSubString("12", '1', '2'));
Console.WriteLine(RemoveSubString("21", '1', '2'));
Console.WriteLine(RemoveSubString("2-1-2", '1', '2'));
Console.WriteLine(RemoveSubString("1-2", '1', '2'));
Console.WriteLine(RemoveSubString("1222222", '1', '2'));
Console.WriteLine(RemoveSubString("2111111", '1', '2'));
Console.WriteLine(RemoveSubString("1-111111", '1', '1'));
Console.WriteLine(RemoveSubString("1-11111--1", '1', '1'));


Вывод

а+б а++б +а+++б+ ++аб++
а+б_а++б_+а+++б+_++аб++
12-------2--------2
12
21
2-12
12
1222222
2111111
1111111
1-111111