Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.72/43: Рейтинг темы: голосов - 43, средняя оценка - 4.72
3 / 3 / 0
Регистрация: 14.11.2011
Сообщений: 22

Анаграммы(олимпиадная задача)

17.12.2011, 14:17. Показов 8758. Ответов 9
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Cтрока S1 называется анаграммой строки S2, если она получается из S2 перестановкой символов. Даны строки S1 и S2. Напишите программу, которая проверяет, является ли S1 анаграммой S2.

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

Первая строка входного файла INPUT.TXT содержит строку S1, вторая - S2. Обе строки состоят только из прописных букв латинского алфавита. Строки не пусты и имеют длину не больше 100000 символов.

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

В выходной файл OUTPUT.TXT выведите YES, если S1 является анаграммой S2, и NO - в противном случае.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
17.12.2011, 14:17
Ответы с готовыми решениями:

Строки.Анаграммы.(Задача сделана,но не выводит результат...)
Даны 2 слова(строки),проверить есть ли эти слова анаграммами(отличаются только порядком букв) // анаграмма].cpp : Defines the entry point...

Олимпиадная задача
Был в прошлом году на олимпиаде по программированию и там была такая задача: После запуска программы пользователь должен начать...

Олимпиадная задача
Дошел до этой олимпиадной задачи и впал в ступор. Нагуглил, что можно решить с помощью матриц, либо с помощью графов, но какого-то...

9
программист С++
 Аватар для sandye51
860 / 600 / 147
Регистрация: 19.12.2010
Сообщений: 2,014
17.12.2011, 14:26
Цитата Сообщение от Abylaikhan Посмотреть сообщение
100000
вы не упали случаем?
сложно даже представить 100000! - число этих самых перестановок
0
3 / 3 / 0
Регистрация: 14.11.2011
Сообщений: 22
17.12.2011, 14:30  [ТС]
Цитата Сообщение от sandye51 Посмотреть сообщение
вы не упали случаем?
сложно даже представить 100000! - число этих самых перестановок
А string ведь может выгребать даже столько
0
 Аватар для I.M.
576 / 559 / 47
Регистрация: 16.12.2011
Сообщений: 1,389
17.12.2011, 14:32
А зачем пробегать все эти перестановки?
Создаете два массива. Каждый на 128 элементов (128 - для удобства доступа. можно всего 26 - по числу прописных латинских символов).
Затем проходите по каждой из строк и увеличиваете элемент массива, соответствующий аски-коду очередного символа строки, на единицу.
А затем вам нужно будет сравнить содержимое этих двух массивов. Если полностью совпало, то анаграмма. Если нет - то нет.

А вообще, раз уж постите тут задачки с какого-то соревнования (это же явно не лаба), то хоть прикладывайте к ним свое решение, пусть и неверное.
1
3 / 3 / 0
Регистрация: 14.11.2011
Сообщений: 22
17.12.2011, 14:42  [ТС]
Цитата Сообщение от I.M. Посмотреть сообщение
А зачем пробегать все эти перестановки?
Создаете два массива. Каждый на 128 элементов (128 - для удобства доступа. можно всего 26 - по числу прописных латинских символов).
Затем проходите по каждой из строк и увеличиваете элемент массива, соответствующий аски-коду очередного символа строки, на единицу.
А затем вам нужно будет сравнить содержимое этих двух массивов. Если полностью совпало, то анаграмма. Если нет - то нет.

А вообще, раз уж постите тут задачки с какого-то соревнования (это же явно не лаба), то хоть прикладывайте к ним свое решение, пусть и неверное.
Сайт acmp.ru попробуй порешать
Cпасибо а код написать на с++ сможешь?
0
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 30
29.06.2013, 13:56
Здравствуйте!
Написал вот такое решение, но на 3 тесте Time Limit:
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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
 
// сортируем строки и сравниваем на идентичность
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    char str[10001];
    gets(str);
    char str2[10001];
    gets(str2);
    int N;
    N = strlen(str);
    std::sort(str, str+N);
    N = strlen(str2);
    std::sort(str2, str2+N);
    if (strcmp(str, str2))
        printf("NO");
    else
        printf("YES");
    return 0;
}
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.06.2013, 14:26
@nuts23, размер массива слишком маленький
1
 Аватар для Olivеr
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
29.06.2013, 14:48
@nuts23,
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
#include <cstring>
#include <cstdio>
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    char str1[100001];
    gets(str1);
    char str2[100001];
    gets(str2);
    int arr1[91], arr2[91];
    const int str1_size = strlen(str1);
    const int str2_size = strlen(str2);
 
    if (str1_size != str2_size) {
        printf("NO");
        return 0;
    }
 
    for (int i = 0; i != str1_size; ++i) {
        ++arr1[ str1[i] ];
        ++arr2[ str2[i] ];
    }
 
    for (int i = 65; i != 91; ++i)
        if ( arr1[i] != arr2[i] ) {
            printf("NO");
            return 0;
        }
    printf("YES");
    return 0;
}
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.06.2013, 15:43
Цитата Сообщение от sandye51 Посмотреть сообщение
вы не упали случаем?
сложно даже представить 100000! - число этих самых перестановок
кто же такие задачи в лоб решает?!

C++
1
2
3
4
5
6
7
8
9
10
11
int Check(char *s, char *t)
{
   int count[128] = {0}, i; 
   for(; *s; ++s)
      ++count[*s];
   for(; *t; ++t)
      --count[*t];
   for(i = 'A'; i <= 'Z' && !count[i]; ++i)
      ;
   return i > 'Z';
}
Цитата Сообщение от I.M. Посмотреть сообщение
Создаете два массива. Каждый на 128 элементов
можно и одним обойтись

Добавлено через 4 минуты
так как длины строк изначально одинаковы, то еще проще:
C++
1
2
3
4
5
6
7
8
9
10
11
12
int Check(char *s, char *t)
{
   int count[128] = {0}, i; 
   for(; *s; ++s, ++t)
   {
      ++count[*s];
      --count[*t];
   }
   for(i = 'A'; i <= 'Z' && !count[i]; ++i)
      ;
   return i > 'Z';
}
вариаций несколько, главное, сложность линейная
0
36 / 36 / 2
Регистрация: 28.04.2013
Сообщений: 110
29.06.2013, 16:35
ACCEPTED

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
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    string str1, str2;
    int s1[27], s2[27];
    memset(s1, 0, sizeof(s1));
    memset(s2, 0, sizeof(s2));
    
    cin >> str1 >> str2;
    
    if(str1.size() != str2.size())
    {
        cout << "NO";
        return 0;
    }
    
    for(int i = 0; i < str1.size(); ++i)
    {
        s1[str1[i] - 'A']++;
        s2[str2[i] - 'A']++;
    }
    
    for(int i = 0; i < 27; ++i)
        if(s1[i] != s2[i])
        {
            cout << "NO";
            return 0;
        }
    
    cout << "YES";
    return 0;
}
Добавлено через 39 секунд
на всякий случай включил проверку длин строк

UPD с одним массивом, решение изящнее, можно задействовать функцию accumulate()
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
29.06.2013, 16:35
Помогаю со студенческими работами здесь

Олимпиадная задача
#include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;iostream&gt; using namespace std; int main() { unsigned int N; cout&lt;&lt;&quot;N=&quot;;...

Олимпиадная задача
Вот наткнулся сегодня на такую задачу: Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда...

Задача на дп (олимпиадная)
Здравствуйте, имеется данная задача, основная проблема состоит в том, что мое решение никак не проходит по времени. Пробовал писать через...

C++. Олимпиадная задача
Здравствуйте! Код не проходит какой-то тест, может алгоритм не правильный. И если не правильный, то как исправить? Помогите найти ошибку....

Олимпиадная задача
Алфавит мурмарианской системы счисления включает три цифры - 1, 2 и 3. Одна из популярных социальных сетей &quot;НаМурмаре&quot; при...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .
Камера 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 с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru