Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 14.05.2017
Сообщений: 19

Уничтожить подпоследовательность в строке

09.01.2018, 11:51. Показов 625. Ответов 16
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Столкнулся с такой проблемой, вводится строка S и строка T. Нужно убрать наименьшее количество букв в строке S, чтобы в ней не встречалась строка T в порядке слева направо(если T=aba, но в строке aaab не встречается T, а в строке aaba встречается). Попытки были, но не знаю как сделать наименьшее возможное количество убранных букв

Спасибо за помощь.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
09.01.2018, 11:51
Ответы с готовыми решениями:

Уничтожить в строке все вхождения подстроки
Заданная строка символов. Уничтожить в нем все вхождения подстроки 'Y + Z ".

Строки: уничтожить в строке запятые перед первой точкой, заменить знаком + все цифры 3я после первой точки
Дано строка длиной n символов, среди которых есть хотя бы одна точка. превратить последовательность s1, s2, ... sn, уничтожив в ней все...

В строке символов найти максимальную подпоследовательность символов, являющуюся палиндромом
Народ, помогите пожалуйста. Нужно написать программу, используя динамический массив. Вот условие задачи: В строке символов найти...

16
230 / 199 / 71
Регистрация: 21.10.2016
Сообщений: 449
09.01.2018, 13:14
Так что ли?
Java
1
2
3
4
5
6
7
8
9
10
11
class Replacement {
 
    public static void main(String[] args) {
        String s1 = "aaab";
        String s2 = "aaba";
        String t = "aba";
 
        System.out.println(s1.replace(t, ""));
        System.out.println(s2.replace(t, ""));
    }
}
Bash
1
2
3
const@mate ~/progs $ java Replacement
aaab
a
0
Эксперт Java
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
09.01.2018, 13:19
Цитата Сообщение от Хм Посмотреть сообщение
Так что ли?
видимо немного хитрее например t=aba, s=aababa
1
0 / 0 / 0
Регистрация: 14.05.2017
Сообщений: 19
09.01.2018, 18:26  [ТС]
Строки S и T могут быть какими удобно + нужно убрать минимальное количество букв. Гораздо хитрее.
0
 Аватар для HighPredator
6045 / 2160 / 753
Регистрация: 10.12.2010
Сообщений: 6,005
Записей в блоге: 3
10.01.2018, 10:11
По моему представлению здесь нужно плясать от расстояния Хэмминга. Причем так, чтобы (с аналитической точки зрения) при удалении символов из S, ее части плохо схлопывались в T.

Добавлено через 18 секунд
А так, да, развеселая задачка.
0
 Аватар для Aviz__
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
10.01.2018, 15:21
мне думается так:
Java
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.ArrayList;
 
/** */
public class TestCombinat {
    private static ArrayList<SubstrInfo> combination = new ArrayList<>();
 
    private static boolean isContain(String newSubstr) {
        for (SubstrInfo tmpSub : combination){
            if (tmpSub.getContent().equalsIgnoreCase(newSubstr))
                return true;
        }
       return false;
    }
 
    private static String getDeleteSubstr() {
        int minTmp = Integer.MAX_VALUE;
        String strForReturn = null;
        for (SubstrInfo tmpSub : combination){
            int carrVal = tmpSub.getParamForDeleteThisSubstr();
            if (carrVal < minTmp)
                minTmp = carrVal;
        }
        for (SubstrInfo tmpSub : combination){
            if (tmpSub.getParamForDeleteThisSubstr() == minTmp)
                strForReturn =tmpSub.getContent();
        }
        return strForReturn;
    }
 
    private static void fillStatistic(String containerStr) {
        for (SubstrInfo tmpSub : combination){
            int indexPartSubstr = containerStr.indexOf(tmpSub.getContent());
            while (indexPartSubstr != -1 ) {
                indexPartSubstr = containerStr.indexOf(tmpSub.getContent(),indexPartSubstr + 1);
                tmpSub.addFrequency();
            }
        }
    }
 
    public static void main(String[] args) {
        String s1 = "aababa";
        String t = "aba";
        for (int bInd = 0; bInd < t.length(); bInd++) {
            for (int eInd = bInd + 1; eInd <= t.length(); eInd++) {
                if (!isContain(t.substring(bInd,eInd)))
                    combination.add(new SubstrInfo(t.substring(bInd,eInd)));
            }
        }
        fillStatistic(s1);
        System.out.println(getDeleteSubstr());
    }
}
//####
public class SubstrInfo {
    private String content;
    private int lenStrContent;
    private int frequency = 0;
    private int paramForDeleteThisSubstr = 0;
 
    public SubstrInfo(String content) {
        this.content = content;
        this.lenStrContent = content.length();
    }
 
    public void addFrequency() {
        frequency++;
        paramForDeleteThisSubstr = lenStrContent + frequency;
    }
 
    
    public String getContent() {
        return content;
    }
 
    public int getParamForDeleteThisSubstr() {
        return paramForDeleteThisSubstr;
    }
}
0
Эксперт Java
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
10.01.2018, 15:50
код пишет b
что это значит?
0
 Аватар для Aviz__
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
10.01.2018, 17:51
что эта минимальная часть подстроки T, которую нужно убрать в строке S, чтобы нельзя было найти целую T в S.
0
Эксперт Java
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
10.01.2018, 21:16
убираем первую b - остается aaaba, убираем вторую b - aabaa, оба варианта, очевидно, неправильные
0
 Аватар для Aviz__
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
11.01.2018, 08:57
сразу 2 b нужно убирать
0
Эксперт Java
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
11.01.2018, 12:01
Достаточно убрать одно а же
0
 Аватар для Aviz__
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
11.01.2018, 12:12
Цитата Сообщение от xoraxax Посмотреть сообщение
одно а же
это несомненно)! Но, мне пришло такое решение...
0
0 / 0 / 0
Регистрация: 14.05.2017
Сообщений: 19
15.01.2018, 10:52  [ТС]
Цитата Сообщение от Aviz__ Посмотреть сообщение
мне думается так:
Java
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.ArrayList;
 
/** */
public class TestCombinat {
    private static ArrayList<SubstrInfo> combination = new ArrayList<>();
 
    private static boolean isContain(String newSubstr) {
        for (SubstrInfo tmpSub : combination){
            if (tmpSub.getContent().equalsIgnoreCase(newSubstr))
                return true;
        }
       return false;
    }
 
    private static String getDeleteSubstr() {
        int minTmp = Integer.MAX_VALUE;
        String strForReturn = null;
        for (SubstrInfo tmpSub : combination){
            int carrVal = tmpSub.getParamForDeleteThisSubstr();
            if (carrVal < minTmp)
                minTmp = carrVal;
        }
        for (SubstrInfo tmpSub : combination){
            if (tmpSub.getParamForDeleteThisSubstr() == minTmp)
                strForReturn =tmpSub.getContent();
        }
        return strForReturn;
    }
 
    private static void fillStatistic(String containerStr) {
        for (SubstrInfo tmpSub : combination){
            int indexPartSubstr = containerStr.indexOf(tmpSub.getContent());
            while (indexPartSubstr != -1 ) {
                indexPartSubstr = containerStr.indexOf(tmpSub.getContent(),indexPartSubstr + 1);
                tmpSub.addFrequency();
            }
        }
    }
 
    public static void main(String[] args) {
        String s1 = "aababa";
        String t = "aba";
        for (int bInd = 0; bInd < t.length(); bInd++) {
            for (int eInd = bInd + 1; eInd <= t.length(); eInd++) {
                if (!isContain(t.substring(bInd,eInd)))
                    combination.add(new SubstrInfo(t.substring(bInd,eInd)));
            }
        }
        fillStatistic(s1);
        System.out.println(getDeleteSubstr());
    }
}
//####
public class SubstrInfo {
    private String content;
    private int lenStrContent;
    private int frequency = 0;
    private int paramForDeleteThisSubstr = 0;
 
    public SubstrInfo(String content) {
        this.content = content;
        this.lenStrContent = content.length();
    }
 
    public void addFrequency() {
        frequency++;
        paramForDeleteThisSubstr = lenStrContent + frequency;
    }
 
    
    public String getContent() {
        return content;
    }
 
    public int getParamForDeleteThisSubstr() {
        return paramForDeleteThisSubstr;
    }
}
Небольшая поправочка:
Я задал вопрос из-за того, что мой код(с перебором все вариантов(например всех n-подряд букв(n - строка T)) занимал много времени(был криво реализован). Ограничение по времени: одна секунда. Строка до миллиона символов, дело не в неправильности решения, а в "неоптимизированности". Переборное решение занимает много времени, а другого я придумать не смог. Проблема состоит только во времени. Это решение не совсем перебор, но работает долго.
0
Эксперт Java
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
15.01.2018, 10:56
JustHacker,
так ты свое решение то выложи, может подумаем и сделаем быстрее
0
0 / 0 / 0
Регистрация: 14.05.2017
Сообщений: 19
15.01.2018, 11:00  [ТС]
Перебором если только(типа S=aaba, t=ab, перебираем для каждых двух подряд идущих букв, и так пока не уничтожим). Для больших строк нужна оптимизация.
0
 Аватар для Aviz__
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
15.01.2018, 11:33
Так я из t делаю всевозможные комбинации подстрок, слева направо и потом, считаю, сколько этих кусочков входит в s. Затем, выбираю минимальный кусочек.
0
15 / 15 / 1
Регистрация: 15.01.2018
Сообщений: 42
16.01.2018, 10:29
Вот решения(правильные, на java не получилось)
С++:
Кликните здесь для просмотра всего текста
C++
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int MX = 10 * 1000 + 7;
const int MT = 1007;
const int ALPH = 52;
 
int dp[MX][MT];
char type[MX][MT];
 
char s[MX], t[MX];
 
void go(int x, int y) {
    if (type[x][y] == 0) return;
    if (type[x][y] == 1) {
        go(x - 1, y - 1);
        printf("%c", s[x - 1]);
    } else if (type[x][y] == 2) {
        go(x - 1, y);
    } else {
        go(x - 1, y);
        printf("%c", s[x - 1]);
    }
}
 
int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    scanf("%s", s);
    scanf("%s", t);
    int n = strlen(s);
    int m = strlen(t);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i] == t[j]) {
                if (dp[i + 1][j + 1] < dp[i][j] + 1) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    type[i + 1][j + 1] = 1;
                }
                if (dp[i + 1][j] < dp[i][j]) {
                    dp[i + 1][j] = dp[i][j];
                    type[i + 1][j] = 2;
                }
            } else {
                if (dp[i + 1][j] < dp[i][j] + 1) {
                    dp[i + 1][j] = dp[i][j] + 1;
                    type[i + 1][j] = 3;
                }
            }
        }
    }
    int resy = 0;
    for (int j = 0; j < m; j++) {
        if (dp[n][j] > dp[n][resy]) {
            resy = j;
        }
    }
    go(n, resy);
    printf("\n");
}

Python:
Кликните здесь для просмотра всего текста
Python
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
import sys
import os
 
sys.stdin = open('in', 'r')
 
s = input()[::-1]
t = input()[::-1]
n = len(t)
f = [0] * n
p = []
 
for c in s:
    last = [0] * n
    p.append(last)
    for i in range(n - 1, -1, -1):
        last[i] = int(t[i] != c)
        f[i] += last[i]
        if i and f[i] <= f[i - 1]:
            last[i] = 2
            f[i] = f[i - 1] + 1
 
bst = max((f[i], i) for i in range(n))[1]
for cur, c in zip(reversed(p), reversed(s)):
    if cur[bst]:
        print(c, end='')
    if cur[bst] == 2:
        bst -= 1
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
16.01.2018, 10:29
Помогаю со студенческими работами здесь

В строке символов найти максимальную подпоследовательность символов, являющуюся палиндромом
Народ, помогите пожалуйста. Нужно написать программу, используя динамический массив. Вот условие задачи: В строке символов найти...

Уничтожить вектор
После работы остается вектор с ненужными более данными. Нужно его удалить совсем. Может какая функция есть?

Уничтожить зеркало
Где-то года 2 стояла переадресация с домена www.домен.ру на www.поддомен.домен.ру Теперь сделал на www.домен.ру отдельный сайт, стал...

Уничтожить зомби!
Друзья, у нас есть список зомби: enemy_list= и список подлистов (отрядов), в которых они есть: comands_list=cолдат_1&quot;,...

Уничтожить стек
Не могу сделать уничтожение стека, стек по шаблону делал: #include &lt;vcl.h&gt; #pragma hdrstop #include &lt;iostream.h&gt; #pragma...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Новые блоги и статьи
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Символьное дифференцирование
igorrr37 13.02.2026
/ * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru