Member 13633241 Ответов: 3

Это вопрос программирования


Учитывая две строки одинаковой длины, вы должны сказать, идентичны ли они обе строки.

Две строки S1 и S2 считаются идентичными, если какая-либо из перестановок строки S1 равна строке S2. подробнее см. Пример объяснения.

Ввод :

Первая строка, содержит целочисленная "Т", обозначающий "нет". из тестовых случаев.
Каждый тест состоит из одной строки, содержащей две разделенные пробелами строки S1 и S2 одинаковой длины.
Выход:

Для каждого тестового случая, если какая-либо из перестановок строки S1 равна строке S2, выведите YES, иначе выведите NO.
Ограничения:

1<= T <=100
1<= |S1| = |S2| <= 10^5
Строка состоит только из строчных букв.
Примечание : Используйте Только Концепцию Хэширования . Попробуйте сделать это в O(длина строки) .

ВХОДНОЙ СИГНАЛ ОБРАЗЦА
3
Сумит Мицу
амбудж Джамба
Абхи хибб
ПРИМЕР ВЫВОДА
ДА
ДА
НЕТ

Что я уже пробовал:

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

int main()
{   
    int n,j,f=0,c,d;
    char str1[100000];
    char str2[100000];
    std::cin>>n;
    while(n--)
    {   
        std::cin.getline(str1,100000);
        std::cin.getline(str2,100000);
        c=strlen(str1);
        d=strlen(str2);
        for(int i=0;i<c;i++)
        {
            for(j=0;j<d;j++)
            {
                if(str1[i]==str2[j])
                {
                    f++;
                }
            }
        }
       
        if(f==c)
        {
            std::cout<<"\nYES";
        }
        else 
        {
            std::cout<<"\nNO";
        }
    }
    
    return 0;
}


Его вывод в 1-м случае-да, но в другом случае-неверен.

3 Ответов

Рейтинг:
2

Member 13889953

#include <iostream>
#include <string.h>
#include <stdlib.h>

использование пространства имен std;

тап_п() {
инт, Т,Я,J;
cin>>t;
while(t--)
{
char s1[100000], s2[100000];
cin>>s1> & gt;s2;
если(strlen(s1)!=strlen(s2))
{
соиь<&ЛТ;"нет"на<<епси;
перерыв;
}
for(i=0;i<strlen(s1);i++)
{
//cout<<s1[i];
for(j=0;j<strlen(s2);j++)
{
если(s1[i]==s2[j])
{
если(i==(strlen(s1)-1))
{
cout<<"YES"<<endl;
}
перерыв;
}
если(с J==(функция strlen(S2 с)-1) &&усилителя; С1[я]!=С2[Дж])
{
соиь<&ЛТ;"нет"на<<епси;
перерыв;
}
}
если(s1[i]==s2[j])
{
продолжить;
}

если(с J==(функция strlen(S2 с)-1) &&усилителя; С1[я]!=С2[Дж])
{

перерыв;
}
}
}
}


Patrice T

Ваш алгоритм ошибочен.

Рейтинг:
0

Rick York

У вас в основном написана часть сравнения, но вы не отделяете строки друг от друга в каждой строке. Вы должны сделать это в первую очередь. Помните, что они разделены пробелом, так что все, что вам нужно сделать, это найти пространство. Символы до пробела переходят в первую строку, а символы после пробела-во вторую строку. Не забудьте завершить строки нулевым символом или сначала инициализировать их всеми нулями. Вот простой способ их инициализации :

char str1[100000] = {0};

Возвращаясь к вашему сравнению, это не будет операцией O(длины). Вам нужен только один цикл для сравнения, и вы должны сравнить str1[i] с str2[i]. Кроме того, не звоните сначала strlen, потому что это не нужно. Просто цикл, пока вы не нажмете нулевой символ в строке. Вы также должны сравнить их тоже, потому что если обе строки не имеют своего конечного null в одном и том же месте, то они не совпадают.


Рейтинг:
0

Patrice T

Эта проблема, очевидно, является соревнованием по программированию, приятно дать ссылку.

- первая проблема: вы используете f чтобы подсчитать совпадения, но после первого теста вы забыли сбросить его значение для следующего теста.

- Вторая проблема: ваш алгоритм неверен.
с вашим алгоритмом
Абхи хибб это да потому что спички есть 0+2+1+1=4, b соответствует 2 раза
хибб Абхи это да потому что спички есть 1+1+1+1=4, 2 b соответствуют одному и тому же b
все abcdefghijklmnopqrstuvwxyz - это да, любая буква находит совпадение

[Обновление]
Для тех, кто интересуется, вот несколько тестовых случаев. Если вы справляетесь с ними правильно, ваш алгоритм должен быть правильным:
abbccc ccacbb да
aabbcc bccccca нет
bccccca aabbcc нет
aabbcc abcdef нет