Оптимизация алгоритма

170

13 января 2019, 16:40

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

#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;
      }
   }
}

Answer 1

Не влезает в комментарий =(

Я видимо сейчас разверну просто комментарий от pavel.

Во-первых, строки точно не эквивалентны, если их размеры не совпадают.

Если совпадают, то тогда эквивалентность строк сводится к эквивалентности множеств символов, из которых они состоят ( с учётом повторений).

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

А одинаковы они будут если количество входящих в множество символов одинаково.

То есть если Вы научитесь для каждого запроса считать количество символов a, b, c, ..., z в подстроке (для каждого символа за O(1), за константное время), то вы за O( N * 26) = O(N) сможете ответить на все запросы Плюс ещё потратите O(|S|) на считывание и обработку исходной строки.

Чтобы за O(1) вычислять количество конкретных символов в диапазоне строке, для каждого символа заведём массив, размером с длину строки (26 * 5 * 10^5 = 130Mb), где в i-ой позиции будем хранить сумму вхождений данного символа, с начала строки до текущей позиции. Ну то есть sum[i] будет равно количеству вхождений конкретного символа в подстроке S[0..i]. Тогда чтобы найти количество символов в подстроке i,j просто вычтем из sum[j] sum[i-1] - и таким образом получим количество вхождений конкретного символа в диапазоне [i..j] = sum[j] - s[i-1].

Пример: строка abbaa

Тогда массив sum для a:

11123

Для b:

01222

P.S. Если оставите ссылочку на задачу - буду очень благодарен, хоть смогу проверить прав ли я =)