Задача

Имеются две строки $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

Код

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);
	}
}

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$ , воспользуемся функцией . Если попадаем в первый вариант решения задачи, то выводим $A$ . Иначе, создаём цикл, который будет удалять символы в конце первой строки и символы в начале второй, пока они не будут равны. Затем из строки $B$ удаляем элементы, которые входят в строку $A$ , и на выход подаём строку $C$ , которая состоит из строки $A$ и оставшихся элементов строки $B$ .

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: слияние строк

e-olymp 9407. Слияние строк