Красивая строка

@85959594 · Регистрация: 26.06.2021

Студворк — интернет-сервис помощи студентам

Условие задачи простое, вам задана строка s состоящая только из букв английского языка. Обозначим длину строки как целое число n (1≤n≤100). Строка является красивой если каждый ее элементы попарно различный то есть если в строке нету такой пары i, j (1≤i<j≤n) что si = sj В строке s вам нужно найти количество красивых подстрок.

Пример 1:
входные данные:
abb
выходные данные:
4
Пример 2:
входные данные:
abB
выходные данные:
6

@Yetty · 27.06.2021, 00:31

алгоритм решения понятен. подстроки строки

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// подстроки строки
#include <iostream>
#include <string>
using namespace std;
 
int main()
{   
    string s="abcd";
    size_t n=s.size();
    
    for (size_t i = 0; i < n; i++)           
        for (size_t j = 1; j <= n-i; j++)
            cout << s.substr(i,j) << "\n";   
    
system("pause");
return 0;
}

OUTPUT:
a
ab
abc
abcd
b
bc
bcd
c
cd
d

проверить на наличие пары одинаковых символов

но прежде объясните почему у Вас такие выходные данные:
строка:
abb
подстроки, перебор в цикле:
a
ab
abb - в этой подстроке одинаковая пара символов
b
bb - в этой подстроке одинаковая пара символов
b

ответ был бы 4, но 2 последние оставшиеся подстроки совпадают, поэтому ответ 3. или в моих расчётах ошибка ?

@TheCalligrapher · 27.06.2021, 05:31

Сообщение от 85959594

найти количество красивых подстрок

Как определяется уникальность подстрок? Две одинаковых по содержанию подстроки, но имеющих разные позиции в исходной строке - считаются как разные подстроки или нет?

Добавлено через 14 минут

Сообщение от Yetty

алгоритм решения понятен. подстроки строки
проверить на наличие пары одинаковых символов

Ну это фактически "алгоритм", полученный путем лобового переписывания условия задачи на ЯВУ.

Алгоритм решения: "скользящее окно", то есть очередь. Новые символы попадают в очередь справа и уходят из очереди слева.

1. Берем из строки очередной символ X (пока они есть)
2. Если символа X еще нет в очереди, то просто добавляем X в очередь справа и переходим на 1.
3. Если символ X уже присутствует в очереди, то генерируем все возможные подстроки очереди, начинающиеся с ее начала.
4. Удаляем первый символ из очереди и переходим на 2.

5. По завершению обработки строки генерируем все возможные подстроки оставшейся очереди, начинающиеся с ее начала.

@Yetty · 27.06.2021, 12:11

определяется общее количество подстрок соответствующих условию (не только уникальных)

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
#include <iostream>
#include <string>
using namespace std;
 
bool f (string const&s)
{   
    size_t size=s.size();
    if (size==1) return true;
    for (size_t i = 0; i < size; i++)
        for (size_t j = i+1; j < size; j++)
            if(s[i]==s[j]) return false;
    return true;
}
 
int main()
{   
    string s;
    cout << "String [ENG letters]:\n";
    cin >> s;
    
    size_t n=s.size(), count=0;   
    
    for (size_t i = 0; i < n; i++)           
        for (size_t j = 1; j <= n-i; j++)        
            if(f(s.substr(i,j))) count++;           
            
    cout << "count=" << count << "\n";        
    
system("pause");
return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .

@85959594 0 / 0 / 0 Регистрация: 26.06.2021 Сообщений: 8

	Красивая строка 26.06.2021, 22:14. Показов 2484. Ответов 3 Метки нет (Все метки) Условие задачи простое, вам задана строка s состоящая только из букв английского языка. Обозначим длину строки как целое число n (1≤n≤100). Строка является красивой если каждый ее элементы попарно различный то есть если в строке нету такой пары i, j (1≤i<j≤n) что si = sj В строке s вам нужно найти количество красивых подстрок. Пример 1: входные данные: abb выходные данные: 4 Пример 2: входные данные: abB выходные данные: 6 0

Красивая строка

Решение