3

Я не смог четко сформулировать вопрос. Но тем не менее вот:

Например, я имею строку "синхрофазотрон" и подстроку "схрон". Функция должна вернуть true, так как данную подстроку можно получить, если пропускать некоторые символы. Суть в том, что нужно сохранить очередность, подстроки хранятся в массиве строк. Есть ли в Java встроенные функции, которые смогут это сделать? У меня была идея, преобразовать подстроку в регулярное выражение, что-то типа "с*х*р*о*н" и использовать matches().

UPD:

По поводу регулярных выражений. Преобразование строки в регулярное выражение и использовать matches() не так уж и трудно реализовать. Но что если у тебя массив подстрок насчитывает больше сотни тысяч элементов, и некоторые из них могут достигать в длине 20 символов?

1
  • 1
    Корректнее будет это назвать подпоследовательностью, а не подстрокой. Регулярное выражение, пожалуй, самое короткое и понятное решение, если нужно быстрее, то уточните ограничения. Еще можете примеры кода в английской версии посмотреть: 1, 2 Commented 30 мая 2017 в 19:40

3 ответа 3

2

Вроде простой же алгоритм. Идем по символам искомой подпоследовательности и пытаемся найти первый такой символ в основном слове. Если находим, продолжаем поиск следующего символа подпоследовательности, но уже с позиции <предыдущий найденный символ + 1>. И так пока либо не сможем найти очередной символ искомой подпоследовательности в слове, либо пока не дойдем алгоритмом до конца.

@Test
public void ttt(){
    String sfzt = "синхрофазотрон";
    String shron = "схрон";

    int lastPos = 0;
    boolean found = true;
    for(char a : shron.toCharArray()){
        int pos = sfzt.indexOf(a, lastPos);
        if(pos == -1){
            found = false;
            break;
        }
        lastPos = pos + 1;
    }
    System.out.println(found);
}
0
0

Итерируем и проверяем:

public static boolean containsSequence(String string, String substring) {
    int lastIndex = 0;
    for (int i = 0; i < substring.length(); i++) {
        int index = string.substring(lastIndex).indexOf(substring.charAt(i));
        if (index == -1)
            return false;
        lastIndex = lastIndex + index + 1;
    }
    return true;
}
0

Встроенных нет, но реализовать не сложно:

public static boolean containsSparse(String string, String substring) {
    int index = 0;
    for (char character : substring.toCharArray()) {
        index = string.indexOf(character, index);
        if (index == -1)
            return false;
        ++index;
    }
    return true;
}
3
  • Читайте вопрос снова =)
    – free_ze
    Commented 30 мая 2017 в 13:38
  • Данный код не учитывает очерёдность символов, а просто проверяет наличие всех символов из подстроки в исходной строке. То есть для строки "синхрофазотрон" и подстроки "ссссс" вернёт true.
    – eugeneek
    Commented 2 июн. 2017 в 10:01
  • Согласен с вашим замечанием. Свой код я исправил. Если вы сами признаёте, что ваш ответ не решает проблемы ТС, почему вы его не исправите? Зачем оставлять неверные ответы, тем более с положительным рейтингом, которые вводят в заблуждение пользователей, столкнувшихся с такой же проблемой.
    – eugeneek
    Commented 2 июн. 2017 в 13:20

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.