Никак не могу выполнить задачу, заданную в ВУЗе - мой алгоритм не работает для больших значений. Подскажите какой-нибудь другой алгоритм для решения задачи или же чем его можно оптимизировать. Вот сама задача:
Вот моё решение:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string S;
int n;
cin >> S >> n;
for ( int i = 0 ; i < n ; i ++ )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
a --; b --; c --; d --;
if ( b - a != d - c )
cout << "NO" << endl;
else
{
string A = S, B = S;
A.erase( A.begin() + b + 1, A.end() );
A.erase( A.begin() , A.begin() + a );
B.erase( B.begin() + d + 1, B.end() );
B.erase( B.begin() , B.begin() + c );
sort( A.begin(), A.end() );
sort( B.begin(), B.end() );
if ( A == B )
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
}
a
- сумму всех букв до текущей. Тогда, если разностьa[j1]-a[i1-1]
не равнаa[j2]-a[i2-1]
- можно смело писать NO. Если равна - ну, надо проверять... У @pavel идея немного другая, но, как мне кажется, там много времени займет обработка и память - все ж таки надо... а, нет, ерунда - порядка 5 МБ. Тогда да. Но я бы скомбинировал оба метода - и его, и мой: мой быстро отбросит заведомо неверное, его - уточнит то, что не отбросит мой... URL задания не дадите, поиграться?