Задача
Имеются две строки $A$ и $B$.
Ваша задача — найти такую строку $C$, которая содержит в себе и $A$ и $B$ в качестве подстрок и является кратчайшей среди всех таких возможных строк.
Подстрокой строки называется последовательно идущая подпоследовательность этой строки. Например, строка $kbtu$ является подстрокой строки $kbtu open$, но строка $fall$ подстрокой не является.
Входные данные
Первая строка содержит строку $A$ $(1 \leqslant |A| \leqslant 10^5)$.
Вторая строка содержит строку $B$ $(1 \leqslant |B| \leqslant 10^5)$.
Гарантируется, что обе строки содержат только строчные латинские буквы.
Выходные данные
Выведите одну строку $C$.
Тесты
| № | Входные данные | Выходные данные |
|---|---|---|
| 1. | compressing single |
compressingle |
| 2. | can you |
canyou |
| 3. | compressiondoneright doner |
compressiondoneright |
| 4. | details tail |
details |
| 5. | essential code |
essentialcode |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static boolean check(StringBuilder a, StringBuilder b) { if(a.length()==b.length()) { for(int i = 0; i < a.length(); i++) { if(a.charAt(i) != b.charAt(i)) return false; } } return true; } public static void main (String[] args) throws java.lang.Exception { int n, m, z; StringBuilder a = new StringBuilder(); StringBuilder b = new StringBuilder(); StringBuilder c = new StringBuilder(); Scanner in = new Scanner(System.in); a.append( in.nextLine()); b.append( in.nextLine()); StringBuilder d = new StringBuilder(b); n = b.length(); m = a.length(); c = new StringBuilder(a.substring(m - n, m)); if(a.toString().contains(b.toString()) != true) { for (int i = 1; i<=n && check(b,c) != true; i++) { b.delete(n - i,m); c.delete(0, 1); } z = c.length(); d.delete(0,z); System.out.print(a); System.out.print(d); } else System.out.print(a); System.exit(0); } } |
Решение
В данной задаче необходимо создать строку $C$, которая будет содержать в себе строки $A$ и $B$. Рассмотрим два варианта решения задачи. Первый – если строка $B$ полностью содержится в строке $A$, то выводим строку $A$. Второй – если строка $B$ содержится в $A$ частично или не содержится вообще, выводим строку $A$ $+$ элементы строки $B$, которых нет в $A$.
Для проверки, находится ли строка $B$ в $A$, воспользуемся функцией contains(). Если попадаем в первый вариант решения задачи, то выводим $A$. Иначе, создаём цикл, который будет удалять символы в конце первой строки и символы в начале второй, пока они не будут равны. Затем из строки $B$ удаляем элементы, которые входят в строку $A$, и на выход подаём строку $C$, которая состоит из строки $A$ и оставшихся элементов строки $B$.
Ссылки
- Условие задачи на e-olymp
- Код программы на ideone.com
- Засчитанное решение на e-olymp