#алгоритм #строки #поиск #подстрока
Надо узнать если ли в строке "раздробленная" подстрока.
Пример:
У нас имеется строка и предпологаемая подстрока, надо просто вывести true или false
если такая трока имеется
Ответ 1
string a, b; cin >> a >> b; int bIndex=0; for (size_t i = 0; i < a.size(); i++) { if (b[bIndex] == a[i]) { bIndex++; } } if (bIndex==b.size()) { cout << "YES"; } else { cout << "NO"; }
#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
#java #строки #подстрока
Столкнулся со следующим непониманием, при переносе кода на c# под java.
Нужно вытащить из строки символов подстроку, взять, начиная с некоторой k-й позиции
n-символов. Собственно, код:
str = "((15+3)+14/2+(7*2)+3^2+(12+(7*2)))";
System.out.println(str.substring(27, 5));
Для меня, как человека немного знакомого с шарпом, код вполне понятный и логичный.
В строке 33 символа, собственно, мне необходимо получить подстроку с 27 - символ (
по 32, символ ). Но в результате я получаю ошибку OutOfBoundException. Причем даже,
если захочу взять с 10 позиции 3 символа. В чем может быть проблема?
Ответ 1
Согласно документации java, метод substring принимает 2 параметра: начальный индекс - откуда начинать вырезать, и конечный индекс - до куда вырезать. substring(int beginIndex, int endIndex)Ответ 2
public String substring(int beginIndex, int endIndex) метод substring принимает начало и конец, а не начала и количество символовОтвет 3
Разобрался, я просто очень плохо знаю java. Нужно указать позиции символов в массиве явно, а не кол-во элементов, которые я хотел бы взять как в c#.Ответ 4
Вывести последние 5 символов поможет код: System.out.println(str.substring(str.length()-5, str.length()));
#python #регулярные_выражения #текст #подстрока
Всем привет. Задача такова - найти самую длинную повторяющуюся последовательность
в исходной подстроке.
Задач элементарно решается перебором. Но хочется одолеть её регулярными выражениями.
Текущий код:
import re
def repeat_inside(text):
m = re.findall(r'((\w+)\2+)', text)
print('исходный текст = {}, результат поиска = {}'.format(text, m[0][0]))
return m[0][0]
if __name__ == '__main__':
assert repeat_inside('aabbff') == 'aa'
assert repeat_inside('aaaaa') == 'aaaaa'
assert repeat_inside('aababcc') == 'abab'
assert repeat_inside('abc') == ''
assert repeat_inside('abcabcabab') == 'abcabc'
Результат выполнения:
исходный текст = aabbff, результат поиска = aa
исходный текст = aaaaa, результат поиска = aaaaa
исходный текст = aababcc, результат поиска = aa
Traceback (most recent call last):
File "C:/Users/.../main.py", line 12, in
assert repeat_inside('aababcc') == 'abab'
AssertionError
Пробовал менять регулярное выражение на \w?((\w+)\2+). Это решает проблему с aababcc.
Но ломает другие тесты. Есть ли у кого-то идеи? Можно без ответа, просто подскажите,
пожалуйста, в какую сторону рыть.
Ответ 1
Нашёл решение. Необходимо было использовать lookahead assertion (?=...). Итоговое регулярное выражение: re.findall(r'(?=((.+?)\2+))', text) Итоговый код: import re def repeat_inside(text): match = re.findall(r'(?=((.+?)\2+))', text) return max((x[0] for x in match), key=len, default='') if __name__ == '__main__': assert repeat_inside('aaaaa') == 'aaaaa', "First" assert repeat_inside('aabbff') == 'aa', "Second" assert repeat_inside('aababcc') == 'abab', "Third" assert repeat_inside('abc') == '', "Forth" assert repeat_inside('abcabcabab') == 'abcabc', "Fifth"
Столкнулся со следующим непониманием, при переносе кода на c# под java.
Нужно вытащить из строки символов подстроку, взять, начиная с некоторой k-й позиции n-символов. Собственно, код:
str = "((15+3)+14/2+(7*2)+3^2+(12+(7*2)))";
System.out.println(str.substring(27, 5));
Для меня, как человека немного знакомого с шарпом, код вполне понятный и логичный. В строке 33 символа, собственно, мне необходимо получить подстроку с 27 - символ ( по 32, символ ). Но в результате я получаю ошибку OutOfBoundException. Причем даже, если захочу взять с 10 позиции 3 символа. В чем может быть проблема?
Согласно документации java, метод substring принимает 2 параметра: начальный индекс - откуда начинать вырезать, и конечный индекс - до куда вырезать.
substring(int beginIndex, int endIndex)