e-olymp 5062. Максимальный подпалиндром

10/06/2017 by Тимур Фирсов

Задача

Из данной строки удалите наименьшее количество символов так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).

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

Непустая строка длиной не более [latex]100[/latex] символов. Строка состоит только из заглавных латинских букв.

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

Вывести строку-палиндром максимальной длины, которую можно получить из исходной вычёркиванием нескольких букв. При наличии нескольких решений необходимо вывести одно (любое) из них.

Тесты

№	Входные данные	Выходные данные
1	QWEERTYY	YY
2	QWEERT	EE
3	BAOBAB	BAOAB
4	ABCDCBA	ABCDCBA

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

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string **dp;
int main() {
    string s1,s2;
    long long i,j;
    cin>>s1;
    s2=s1;
    long long m=s1.size()+1;
    reverse(s2.begin(),s2.end());
    dp=new string* [m];
    for(i=0;i<m;i++)dp[i]=new string [m];
    for(i=1;i<m;i++){
        for(j=1;j<m;j++){
            if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+s2[j-1];
            else{
                if(dp[i-1][j].size()>dp[i][j-1].size())dp[i][j]=dp[i-1][j];
                else dp[i][j]=dp[i][j-1];
            }
        }
    }
    cout<<dp[m-1][m-1];
    return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

string **dp;

int main() {

string s1,s2;

long long i,j;

cin>>s1;

s2=s1;

long long m=s1.size()+1;

reverse(s2.begin(),s2.end());

dp=new string* [m];

for(i=0;i<m;i++)dp[i]=new string [m];

for(i=1;i<m;i++){

for(j=1;j<m;j++){

if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+s2[j-1];

else{

if(dp[i-1][j].size()>dp[i][j-1].size())dp[i][j]=dp[i-1][j];

else dp[i][j]=dp[i][j-1];

}

cout<<dp[m-1][m-1];

return 0;

}

Засчитанное решение на e-olymp.

Решение

Так как палиндром читается одинаково как справа налево, так и слева направо, то максимальным подпалиндромом будет наибольшая общая подстрока двух строк: исходной строки [latex]s_1[/latex] и этой же строки, но записанной в обратном порядке [latex]s_2[/latex] (как, если бы мы её читали справа налево). Для нахождения их наибольшей общей подстроки следует заполнить таблицу [latex]D[/latex] размером [latex] (n+1)\times(n+1) [/latex], где [latex]n[/latex]-длина строки. Заполнять таблицу будем методом аналогичным поиску длины наибольшей общей подстроки, но в каждой ячейке [latex]D_{i j}[/latex] таблицы будем хранить наибольшую подстроку строки, содержащей только первые [latex]i[/latex] символов [latex]s_1[/latex], и строки, содержащей только [latex]j[/latex] первых символов [latex]s_2[/latex]. В ячейках [latex]D_{0 j}[/latex] и [latex]D_{i 0}[/latex] будем хранить пустые строки. Если [latex]i[/latex]-й символ строки [latex]s_1[/latex] равен [latex]j[/latex]-ому символу строки [latex]s_2[/latex], то в ячейку [latex]D_{i j}[/latex] запишем конкатенацию строки из ячейки [latex]D_{i-1 j-1}[/latex] и данного символа. Иначе в ячейке [latex]D_{i j}[/latex] будем хранить наибольшую из строк [latex]D_{i-1 j}[/latex] и [latex]D_{i j-1}[/latex]. Таким образом в ячейке [latex]D_{n n}[/latex] будет хранится наибольший подпалиндром исходной строки.

Ссылки

Related Images:

e-olymp 2040. Обычная перестановка.

20/12/2015 by Кондратюк Настя

Задача взята с сайта e-olymp.com.

Условие задачи

По заданным двум строкам a и b следует вывести такую строку x наибольшей длины, которая одновременно является подстрокой перестановки a и подстрокой перестановки b.

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

Состоит из нескольких тестов, каждый их которых содержит две строки. То есть строки 1 и 2 — это первый тест, строки 3 и 4 — второй тест и т.д. Каждая строка состоит из символов нижнего регистра, причём первой строкой в паре является a, а второй строкой b. Максимальная длина каждой строки 1000 символов.

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

Для каждого теста следует в отдельной строке вывести строку x. Если таких строк несколько, то вывести наименьшую в алфавитном порядке.

Тесты

Входные данные	Выходные данные
walking down	nw
the street	et
abcd efg
abbcdd badbc	abbcd

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

#include <iostream>
#include <string>
using namespace std;

int main() {
	string a, b;
	while(getline(cin, a) && getline(cin, b)){
		for(char letter ='a'; letter <= 'z'; ){
			if((a.find(letter)!=string::npos) && 
			   (b.find(letter)!=string::npos)){ /* если буква есть в 
                            обеих строках */
				cout << letter;
				a.erase(a.find(letter),1); /* стираем найденную 
				букву в первой строке */
				b.erase(b.find(letter),1); /* стираем найденную 
				букву во второй строке */
			}
			else letter++; /* если буквы нет в обеих строках,
                        переходим к следующей букве алфавита */
		}
	    cout << endl;
	}

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string a, b;

while(getline(cin, a) && getline(cin, b)){

for(char letter ='a'; letter <= 'z'; ){

if((a.find(letter)!=string::npos) &&

(b.find(letter)!=string::npos)){ /* если буква есть в

обеих строках */

cout << letter;

a.erase(a.find(letter),1); /* стираем найденную

букву в первой строке */

b.erase(b.find(letter),1); /* стираем найденную

букву во второй строке */

}

else letter++; /* если буквы нет в обеих строках,

переходим к следующей букве алфавита */

}

cout << endl;

}

return 0;

}

ideone.com

Засчитанное решение на e-olymp.com.

Решение

Для решения данной задачи необходимо проходя по алфавиту, искать есть ли текущая буква в обеих строках и удалять её. Если буквы нет одновременно в обеих строках, необходимо перейти к следующей букве алфавита.

Related Images:

Ю12.43

18/12/2014 by Сорокина Полина

Задача: Для двух заданных строк символов найти самую длинную общую подстроку. Пробелы и знаки препинания игнорировать, строчные и прописные буквы считать неразличимыми. Например, строки: «Дай вилку! Бок севрюжий кончается» и «Чемпионский кубок достался не нам» содержат общую подстроку «кубок».

Строка а	Строка b	Результат	Комментарий
Q_+wer ty	q!w ert) q	qwert	Тест пройден
`Curiouser and curiouser!’ cried Alice (she was so much surprised, that for the moment she quite forgot how to speak good English); `now I’m opening out like the largest telescope that ever was!	Good-bye, feet!’ (for when she looked down at her feet, they seemed to be almost out of sight, they were getting so far off). `Oh, my poor little feet, I wonder who will put on your shoes and stockings for you now, dears?	tfor good	Тест пройден
Qwe^r ty	qwE r!ty	qwerty	Тест пройден

C++:

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int main() {
	string a, b;
	getline(cin, a);
	getline(cin, b);
	string a2, b2;
	for(auto i: a){
		if(isalpha(i)){
			a2.push_back(tolower(i)); //Избавляемся от всех знаков кроме букв и понижаем регистр.
		}
	}
	for(auto i: b){
		if(isalpha(i)){
			b2.push_back(tolower(i));
		}
	}
	if(a2==b2){
		cout << a2; //Если строки равны, сразу возвращаем значение одной из них.
		return 0;
	}
	string c;
	for(unsigned int i=0; i<a2.size(); i++){ //Сравниваем символы в строках.
		for(unsigned int j=0; j<b2.size(); j++){
			if(a2[i]==b2[j]){
				c.push_back(a2[i]);
				for(unsigned int k=i+1, t=j+1; (k<a2.size())&&(t<b2.size()); k++, t++){
					if(a2[k]==b2[t]){
						c.push_back(a2[k]);	//Те, которые совпали, записываем в новую строку.
					} else {
						break;
					}
				}
				c.push_back(' ');
			}
		}
	}
	unsigned int r=0, max=0; //В получившейся строке считаем, сколько букв в самом большом слове.
	string c2, maxstr;
	for(unsigned int i=0; i<c.size(); i++){
		if(c[i]!=' '){
			r++;
		} else {
			if(r>max){
				max=r;
			}
			r=0;
		}
	}
	for(unsigned int i=0; i<c.size(); i++){ //Ищем слова такой же длины и записываем их в строку для вывода черех пробел.
		if(c[i]!=' '){
			c2.push_back(c[i]);
		} else {
			
			if(c2.size()==max){
				for(auto j: c2){
					maxstr.push_back(j);
				}
				maxstr.push_back(' ');
			}
			c2.clear();
		}
	}
	cout << maxstr;
	return 0;
}

#include <iostream>

#include <string>

#include <cctype>

using namespace std;

int main() {

string a, b;

getline(cin, a);

getline(cin, b);

string a2, b2;

for(auto i: a){

if(isalpha(i)){

a2.push_back(tolower(i)); //Избавляемся от всех знаков кроме букв и понижаем регистр.

}

for(auto i: b){

if(isalpha(i)){

b2.push_back(tolower(i));

}

if(a2==b2){

cout << a2; //Если строки равны, сразу возвращаем значение одной из них.

return 0;

}

string c;

for(unsigned int i=0; i<a2.size(); i++){ //Сравниваем символы в строках.

for(unsigned int j=0; j<b2.size(); j++){

if(a2[i]==b2[j]){

c.push_back(a2[i]);

for(unsigned int k=i+1, t=j+1; (k<a2.size())&&(t<b2.size()); k++, t++){

if(a2[k]==b2[t]){

c.push_back(a2[k]); //Те, которые совпали, записываем в новую строку.

} else {

break;

}

c.push_back(' ');

}

unsigned int r=0, max=0; //В получившейся строке считаем, сколько букв в самом большом слове.

string c2, maxstr;

for(unsigned int i=0; i<c.size(); i++){

if(c[i]!=' '){

r++;

} else {

if(r>max){

max=r;

}

r=0;

}

for(unsigned int i=0; i<c.size(); i++){ //Ищем слова такой же длины и записываем их в строку для вывода черех пробел.

if(c[i]!=' '){

c2.push_back(c[i]);

} else {

if(c2.size()==max){

for(auto j: c2){

maxstr.push_back(j);

}

maxstr.push_back(' ');

}

c2.clear();

}

cout << maxstr;

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		
		String a, b;
		a = in.nextLine();
		b = in.nextLine();
		String a2 = new String();
		String b2 = new String();
		char ch;
		for(int i=0; i<a.length(); i++){
			ch = a.charAt(i);
			if(Character.isLetter(ch)){
				a2+=Character.toLowerCase(ch); //Избавляемся от всех знаков кроме букв и понижаем регистр.
			}
		}
		for(int i=0; i<b.length(); i++){
			ch = b.charAt(i);
			if(Character.isLetter(ch)){
				b2+=Character.toLowerCase(ch); //Избавляемся от всех знаков кроме букв и понижаем регистр.
			}
		}
		
		if(a2==b2){
			System.out.println(a2);//Если строки равны, сразу возвращаем значение одной из них.
		} else {
			String c = new String();
			for(int i=0; i<a2.length(); i++){ //Сравниваем символы в строках.
				for(int j=0; j<b2.length(); j++){
					if(a2.charAt(i)==b2.charAt(j)){
						c+=a2.charAt(i);
						for(int k=i+1, t=j+1; (k<a2.length())&&(t<b2.length()); k++, t++){
							if(a2.charAt(k)==b2.charAt(t)){
								c+=a2.charAt(k);//Те, которые совпали, записываем в новую строку.
							} else {
								break;
							}
						}
						c+=' ';
					}
				}
			}
			int r=0, max=0; //В получившейся строке считаем, сколько букв в самом большом слове.
			String c2 = new String();
			String maxstr = new String();
			for(int i=0; i<c.length(); i++){
				if(c.charAt(i)!=' '){
					r++;
				} else {
					if(r>max){
						max=r;
					}
					r=0;
				}
			}
			for(int i=0; i<c.length(); i++){ //Ищем слова такой же длины и записываем их в строку для вывода черех пробел.
				if(c.charAt(i)!=' '){
					c2+=c.charAt(i);
				} else {
					
					if(c2.length()==max){
						for(int j=0; j<c2.length(); j++){
							maxstr+=c2.charAt(j);
						}
						maxstr+=' ';
					}
					c2 = new String();
				}
			}
			System.out.println(maxstr);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

String a, b;

a = in.nextLine();

b = in.nextLine();

String a2 = new String();

String b2 = new String();

char ch;

for(int i=0; i<a.length(); i++){

ch = a.charAt(i);

if(Character.isLetter(ch)){

a2+=Character.toLowerCase(ch); //Избавляемся от всех знаков кроме букв и понижаем регистр.

}

for(int i=0; i<b.length(); i++){

ch = b.charAt(i);

if(Character.isLetter(ch)){

b2+=Character.toLowerCase(ch); //Избавляемся от всех знаков кроме букв и понижаем регистр.

}

if(a2==b2){

System.out.println(a2);//Если строки равны, сразу возвращаем значение одной из них.

} else {

String c = new String();

for(int i=0; i<a2.length(); i++){ //Сравниваем символы в строках.

for(int j=0; j<b2.length(); j++){

if(a2.charAt(i)==b2.charAt(j)){

c+=a2.charAt(i);

for(int k=i+1, t=j+1; (k<a2.length())&&(t<b2.length()); k++, t++){

if(a2.charAt(k)==b2.charAt(t)){

c+=a2.charAt(k);//Те, которые совпали, записываем в новую строку.

} else {

break;

}

c+=' ';

}

int r=0, max=0; //В получившейся строке считаем, сколько букв в самом большом слове.

String c2 = new String();

String maxstr = new String();

for(int i=0; i<c.length(); i++){

if(c.charAt(i)!=' '){

r++;

} else {

if(r>max){

max=r;

}

r=0;

}

for(int i=0; i<c.length(); i++){ //Ищем слова такой же длины и записываем их в строку для вывода черех пробел.

if(c.charAt(i)!=' '){

c2+=c.charAt(i);

} else {

if(c2.length()==max){

for(int j=0; j<c2.length(); j++){

maxstr+=c2.charAt(j);

}

maxstr+=' ';

}

c2 = new String();

}

System.out.println(maxstr);

}

Даны строки [latex]a[/latex] и [latex]b[/latex]. Сначала переписываем их в строки [latex]a2[/latex] и [latex]b2[/latex], при этом избавляясь от всех символов, кроме букв, и понижая их регистр.

Чтобы выделить все совпадающие комбинации букв, сравниваем каждый символ из [latex]a2[/latex] подряд со всеми символами из [latex]b2[/latex]. Когда находим одинаковые буквы, проверяем уже следующий символ в [latex]a2[/latex] и в [latex]b2[/latex]. Все общие подстроки записываем в строку [latex]c[/latex] через пробел.

Так как в строках может быть несколько общих подстрок наибольшей длины, сначала в строке [latex]c[/latex] считаем, сколько букв в самой длинной подстроке. А после этого ищем слова такой длины и записываем их в строку для вывода через пробел.

Задача на Ideone:
C++
Java

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: общая подстрока

e-olymp 5062. Максимальный подпалиндром

Задача

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

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

Тесты

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

Решение

Ссылки

Related Images:

e-olymp 2040. Обычная перестановка.

Условие задачи

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

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

Тесты

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

Решение

Related Images:

Ю12.43

Related Images: