Можно ли из букв слова X составить слово Y?

@lesya21 · Регистрация: 26.11.2011

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

проверьте , можно ли из букв слова Х составить слово У.Пожалуйста помогите , вобще не понимаю как это делать(

@Deviaphan · 02.12.2011, 19:06

Не по теме:

ХУ знает. Наверное можно.

@AncinetHero · 02.12.2011, 19:11

Алгоритм:
Считываете две строки, пробегаетесь по элементам первой строки:
Если элемент первой строки найдет во второй строке удалить элемент во второй строке.

В конце, если 2 строка пуста, делаете выводы.

@Thinker · 02.12.2011, 19:13

AncinetHero, ваш алгоритм рабочий, но его сложность O(mn), где m и n - длины соответствующих строк. Можно за O(m+n) шагов все сделать)

@dyosick · 02.12.2011, 19:16

Выношу на обсуждение следующий вариант:

К примеру, есть слово "маракама" - это Х, составляем частотный словарь ():
а - 4 (число повторений буквы в слове)
к - 1
м - 2
р - 1
Надо получить слово "мама" - это Y, поступаем аналогично:
а - 2
м - 2

Ну, а дальше сверяем словарь Y со словарем Х.

@AncinetHero · 02.12.2011, 19:16

Мой уровень в программировании еще низок, я согласен =(

@Deviaphan · 02.12.2011, 19:17

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

Можно за m+n шагов все сделать)

Я только за m+n+255 придумал. Если строки короткие, то 255 отбрасывать не буду из сложности.)
Но это для ASCI строк, разумеется.

go · 02.12.2011, 19:22

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

Можно за O(m+n) шагов все сделать)

Без сортировок?

@Thinker · 02.12.2011, 19:28

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<string.h>
int Check(char *s, char *t)
{
   int i, count[256] = {0};
   while(*s)
      ++count[*s++];
   while(*t && --count[*t++] >= 0)
      ;
   return *t == '\0';
}
 
int main()
{
    char x[1024], y[1024];
    fgets(x, 1024, stdin);
    fgets(y, 1024, stdin);
    printf("%s\n", Check(x, y) ? "yes" : "no");
    return 0;
}

Добавлено через 46 секунд

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

Без сортировок?

конечно)

Добавлено через 31 секунду

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

Я только за m+n+255 придумал. Если строки короткие, то 255 отбрасывать не буду из сложности.)
Но это для ASCI строк, разумеется.

Именно не более m+n шагов)

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

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

Мой уровень в программировании еще низок, я согласен =(

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

@easybudda · 02.12.2011, 20:21

Thinker, красиво

Без понятия, что там со сложностью, и очевидно медленнее, за то туманно и запутанно:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <string.h>
    
int main(void){
    char wrd1[BUFSIZ], wrd2[BUFSIZ];
    
    while ( printf("First: ") && scanf("%s", wrd1) == 1 && printf("Second: ") && scanf("%s", wrd2) == 1 ){
        char * p, * p1, * p2;
        for ( p = wrd2; *p; ++p ){
            if ( ( p2 = strchr(wrd2, *p) ) == p ){
                if ( p1 = strchr(wrd1, *p) )
                    while ( ( p2 = strchr(p2+1, *p) ) && ( p1 = strchr(p1+1, *p) ) )
                        ;
                if ( ! p1 )
                    break;
            }
        }
        printf("%s\n", ( *p ) ? "No way!" : "Oh Yeah!");
    }
    
    return 0;
}

@Thinker · 02.12.2011, 22:47

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

Thinker, красиво

Не по теме:

спасибо:)

Не по теме:

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

@easybudda · 02.12.2011, 23:10

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

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

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

@Thinker · 02.12.2011, 23:17

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

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

Имеется в виду средний случай

кстати, у меня так же. Если в строке y первая буква не содержится в строке x, то алгоритм тут же останавливается, поэтому число шагов оценивается двойным неравенством:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?m+1 \leq W(m,n) \leq m + n$ , где m = strlen(x), n=strlen(y)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь 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. На борту пять. . .	Камера 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. Пошагово создадим проект для загрузки изображения. . .

@lesya21 0 / 0 / 0 Регистрация: 26.11.2011 Сообщений: 18

	Можно ли из букв слова X составить слово Y? 02.12.2011, 19:04. Показов 4463. Ответов 12 Метки нет (Все метки) проверьте , можно ли из букв слова Х составить слово У.Пожалуйста помогите , вобще не понимаю как это делать( 0

@Deviaphan
	02.12.2011, 19:06
	Не по теме: ХУ знает. Наверное можно. 0

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	02.12.2011, 19:11
	Алгоритм: Считываете две строки, пробегаетесь по элементам первой строки: Если элемент первой строки найдет во второй строке удалить элемент во второй строке. В конце, если 2 строка пуста, делаете выводы. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	02.12.2011, 19:13
	AncinetHero, ваш алгоритм рабочий, но его сложность O(mn), где m и n - длины соответствующих строк. Можно за O(m+n) шагов все сделать) 0

@dyosick 64 / 64 / 17 Регистрация: 25.08.2008 Сообщений: 178
	02.12.2011, 19:16
	Выношу на обсуждение следующий вариант: К примеру, есть слово "маракама" - это Х, составляем частотный словарь (): а - 4 (число повторений буквы в слове) к - 1 м - 2 р - 1 Надо получить слово "мама" - это Y, поступаем аналогично: а - 2 м - 2 Ну, а дальше сверяем словарь Y со словарем Х. 0

Можно ли из букв слова X составить слово Y?

Решение