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

03/12/2020 by Даниил Кулык

Задача

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

Ссылки

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

e-olymp 1308. Наибольшая грань подстроки

25/12/2018 by Саша Рябова

Условие

Гранью (border, verge, brink) $br$ строки $S$ называется любой собственный префикс этой строки, равный суффиксу $S$.
Строка $S=abaababaabaab$ имеет две грани (не пустые): $ab$ и $abaab$. Строка $S=abaabaab$ также имеет две грани: $ab$ и $abaab$, но вторая грань — перекрывающаяся. Строка длины $n$ из повторяющегося символа, например $aaaaaaaa$ (или $a^8$), имеет $n-1$ грань. Для $S=a^8$ это грани: $a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa$.
Понятие «собственный префикс» исключает грань, совпадающую с самой строкой.
Длина грани — это количество символов в ней.
Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок $S[1..i] (i = 1..n)$ и сохранить их в массиве $br[1..n]$.
Найдите наибольшее значение грани в массиве наибольших граней $br$ для всех подстрок $S$.

Тесты

Входные данные	Выходные данные	Комментарий
$abaabaab$	5	$abaab$ в исходной строке
$abaababaabaab$	6	$abaaba$ в подстроке abaababaabaab
$aaaaaaaa$	7	$aaaaaaa$ в исходной строке
$YM$	0	Грань отсутствует, т.к. префикс и суффикс не могут совпадать с самой строкой, а кроме $Y$ в качестве префикса и $M$ в качестве суффикса вариантов выбора нет
$&#%*%#&$	1	$&$ в исходной строке
$15015105$	2	$15$ в подстроке 15015105

Код задачи

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        int answer = 0;    // Длина наибольшей грани
        for(int i = 1; i < S.length() && S.length() - i > answer; i++) { 
            int j = 0;
            /*
            Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
            i - первый символ очередного суффикса
            j - длина текущей грани и первый символ очередного префикса
            */
            while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){  // Накапливаем длину, пока символы префикса и суффикса совпадают
                j++;
            }
            if (j > answer) answer = j;
        }
        System.out.print(answer);
    }
    
}

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String S = sc.nextLine();

int answer = 0; // Длина наибольшей грани

for(int i = 1; i < S.length() && S.length() - i > answer; i++) {

int j = 0;

Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){ // Накапливаем длину, пока символы префикса и суффикса совпадают

j++;

}

if (j > answer) answer = j;

}

System.out.print(answer);

}

Решение

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

В основе программы лежит алгоритм, идея которого заключается не в переборе подстрок с последующим поиском граней в них (так как это было бы очень ресурсозатратно), а в переборе смещений префикса и суффикса друг относительно друга и вычислении максимальной грани, которую можно получить в каждом из таких смещений. Цикл перебора выглядит следующим образом:

Так как по условию грань не может совпадать со строкой, перебор начнем со случая, когда первый символ суффикса находится на второй позиции в строке, а первый символ префикса — на первой позиции. В каждой следующей итерации первый символ суффикса будет смещаться на одну позицию вправо, но первый символ префикса будет неизменно оставаться на первой позиции. Цикл продолжается до тех пор, пока не дойдем до случая, когда первый символ суффикса будет последним символом строки, и пока количество символов от начала суффикса до конца строки будет больше длины максимальной найденной на данный момент грани (это условие необязательно, но оно ускоряет работу программы, отбрасывая варианты, когда получить более длинную грань уже никаким образом не получится):

for(int i = 1; i < S.length() && S.length() - i > answer; i++) { 
            int j = 0;
            /*
            Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
            i - первый символ очередного суффикса
            j - длина текущей грани и первый символ очередного префикса
            */

for(int i = 1; i < S.length() && S.length() - i > answer; i++) {

int j = 0;

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают.К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.

while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){  // Накапливаем длину, пока символы префикса и суффикса совпадают
                j++;
            }

while(j < S.length() - i && S.charAt(j) == S.charAt(i + j)){ // Накапливаем длину, пока символы префикса и суффикса совпадают

j++;

}

В виду того, что нумерация символов в строке начинается с нуля, переменная $j$ выполняет здесь одновременно роль первого символа префикса и длины текущей грани.

Сравним длину текущей грани с длиной максимальной грани и, если необходимо, обновим значение максимальной.

Отметим, что значение переменной $j$, получаемое в каждой итерации, представляет собой максимально возможную длину грани либо исходной строки (если проверки на совпадение пар символов закончились из-за достижения конца строки), либо подстроки, получаемой путем отбрасывания правой части исходной до того символа, на котором обнаружилось несовпадение.

Ссылки

Код задачи на e-olymp
Код решения на ideone.com

e-olymp 1611. Реверс подстроки

09/12/2018 by Карина Миловская

Задача

Дана строка $s$, в которой выделили подстроку, состоящую из символов с $i$-го по $j$-ый включительно (символы строки $s$ нумеруются с единицы) и поменяли местами $i$-ый символ с $j$-ым и так далее (конвертировали подстроку). Выведите строку $s$ после внесенных изменений.

Входные данные

В первой строке содержится строка $s$ длиной не более $1000$ символов, во второй — два числа $i$ и $j$ $\left ( i \leq j \right ).$

Выходные данные

Выведите строку $s$ после внесенных изменений.

Тесты

Входные данные	Выходные данные
$zbbg \\ 2 \ 3$	$zbbg$
$gaqipkajibk \\ 5 \ 6$	$gaqikpajibk$
$helloworld \\ 5 \ 7$	$helloworld$
$eolymp1611 \\ 7 \ 8$	$eolymp6111$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		String str = in.nextLine();
		char[] s = str.toCharArray();
		int i = in.nextInt();
		int j = in.nextInt();
		for(int b = i - 1, c = j - 1; b < c; b++, c--) {
			char k = s[b];
			s[b] = s[c];
			s[c] = k;
		}
	System.out.println(s);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

String str = in.nextLine();

char[] s = str.toCharArray();

int i = in.nextInt();

int j = in.nextInt();

for(int b = i - 1, c = j - 1; b < c; b++, c--) {

char k = s[b];

s[b] = s[c];

s[c] = k;

}

System.out.println(s);

}

Решение

Для решения задачи вводим строку $str$ и преобразуем её в массив символов $(char)$. Далее в цикле конвертируем подстроку и выводим строку $s$ после внесенных изменений.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

e-olymp 1078. Степень строки

04/07/2017 by Хоба Юрий

Постановка задачи

Обозначим через [latex]a\cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a=[/latex] «abc» и [latex]b=[/latex] «def», то [latex]a\cdot b=[/latex] «abcdef».
Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

[latex]a^{0}=[/latex] «» (пустая строка)
[latex]a^{n+1}=a\cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

Входные данные:

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

Выходные данные:

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

№	Входные данные	Выходные данные
1	abcabcabc	3
2	aaaaaaaaaa	10
3	ollollo	1
4	pjpjpjpj	4

Посмотреть работу программы на примере приведенных выше тестов можно на сайте ideone.

Решение

import java.util.*;

class task6 
{
	static public int StringPow(final String str)
	{
		int size = str.length();
		int pow = 1;
		for (int i=1; i<=size/2; i++)
		{
			if (size % i != 0)
				continue;
			String sub1 = new String(str.substring(0, i));
			boolean found = true;
			for (int j = i; j < size; j+=i)
			{
				String sub2 = new String(str.substring(j, j+i));
				if (!sub1.equals(sub2))
				{
					found = false;
					break;
				}
			}
			if (found)
			{
				pow = (size/i);
				break;
			}
		}
		return pow;
	}
	
	static public void main (String[] argv)
	{
		String str;
		Scanner in = new Scanner(System.in);
		while (in.hasNext())
		{
			str = in.nextLine();
			System.out.println(StringPow(str));
		}
		in.close();
	}
}

import java.util.*;

class task6

{

static public int StringPow(final String str)

{

int size = str.length();

int pow = 1;

for (int i=1; i<=size/2; i++)

{

if (size % i != 0)

continue;

String sub1 = new String(str.substring(0, i));

boolean found = true;

for (int j = i; j < size; j+=i)

{

String sub2 = new String(str.substring(j, j+i));

if (!sub1.equals(sub2))

{

found = false;

break;

}

if (found)

{

pow = (size/i);

break;

}

return pow;

}

static public void main (String[] argv)

{

String str;

Scanner in = new Scanner(System.in);

while (in.hasNext())

{

str = in.nextLine();

System.out.println(StringPow(str));

}

in.close();

}

Описание решения

Получая строку str из потока ввода, вызываем функцию static public int StringPow(final String str) и передаем полученную строку в качестве входного параметра. Функция StringPow возвращает значение типа int — наибольшую степень строки, которую программа и передаст в поток вывода в качестве выходных данных.

Минимальной степенью строки может быть число [latex]1[/latex] — в том случае, если в заданной строке [latex]s[/latex] нет повторяющихся подстрок. Максимальной же степенью строки может быть количество символов, из которых строка состоит — в том случае, если строка состоит из одного повторяющегося символа. В этом случае этот символ и будет считаться повторяющейся подстрокой.

Получив в качестве входного аргумента строку str, предположим внутри тела функции StringPow, что степень данной строки равна [latex]1[/latex] ( int pow = 1;) на тот случай, если бо́льшую степень найти не удастся.

Так как нужно найти число повторений подстроки минимального размера в строке str, будем проверять все подстроки размером от [latex]1[/latex] символа до size/2, где size — длина строки. Строка не может состоять из повторяющейся подстроки размером меньше [latex]1[/latex] или больше половины строки. Отсюда цикл for (int i=1; i<=size/2; i++).

Сразу будем отсеивать подстроки, из повторений которых строка не может состоять из-за несоответствия количества символов строки и подстроки ( if (size % i != 0) continue;). К примеру, строка длиной [latex]8[/latex] символов не может состоять из повторений подстроки длиной [latex]3[/latex] символа.

Запоминаем эту подстроку String sub1 = new String(str.substring(0, i));, а затем будем сравнивать с каждой следующей подстрокой такого же размера String sub2 = new String(str.substring(j, j+i)); во внутреннем цикле, предполагая перед этим, что мы нашли нужную нам подстроку ( boolean found = true;); если сверяемые подстроки различаются ( if (!sub1.equals(sub2))) — значит рассматриваемая подстрока sub1 искомой подстрокой не является. Прерываем действие внутреннего цикла и переходим к следующей подстроке, длиной на 1 символ больше. Если же строка полностью состоит из подстроки sub1 находим степень строки — число повторений подстроки в строке, иначе говоря, делим размер строки на размер подстроки ( pow = (size/i);).

Посмотреть решение задания можно на сайте e-olymp.

java@Cat

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

Tag Archives: подстрока

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

Задача

Входные данные

Выходные данные

Тесты

Код

Решение

Ссылки

e-olymp 1308. Наибольшая грань подстроки

Условие

Тесты

Код задачи

Решение

Ссылки

e-olymp 1611. Реверс подстроки

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение

Ссылки

e-olymp 1078. Степень строки

Постановка задачи

Входные данные:

Выходные данные:

Тесты

Решение

Описание решения