Блог

Учитывая строку и подстроку, а также индекс начальной и конечной точек, я хочу иметь возможность находить количество вхождений этой подстроки в привязке. Например, задана строка «ACACTACG», и я хочу найти количество вхождений подстроки «AC» от 3 до 7 (если первый индекс равен 1). Приведенный выше пример выдает результат 2. С 3 по 7 мы имеем «ACTAC», в котором подстрока «AC» встречается 2 раза. Кажется, я не могу закодировать это на C ;

Это проблема C конкурса начинающих AtCoder 122:https://atcoder.jp/contests/abc122/tasks/abc122_c

Мне ДЕЙСТВИТЕЛЬНО УДАЛОСЬ ЭТО ЗАКОДИРОВАТЬ, но лимит времени превышен. Мне нужен более простой подход к этому.

Вот мое представление результата TLE:

 #include <iostream>

using namespace std;

int main()
{
    int N, Q;
    string s;
    cin >> N >> Q >> s;

    for(int i = 0; i < Q; i  )
    {
        int l, r;
        cin >> l >> r;
        if(l >= r)
        {
            cout << 0 << endl;
            break;
        }
        int count = 0;
        for(int j = l - 1; j < r; j  )
        {
            if(s[j] == 'A' amp;amp; s[j   1] == 'C' amp;amp; j != r - 1)
            {
                count  ;
                j  ;
            }
        }
        cout << count << endl;
    }

    return 0;
}
  

После выполнения некоторых математических расчетов мне удалось обнаружить, что причина, по которой я получил TLE, заключается в том, что мой код содержит примерно 10 ^ 10 инструкций, в то время как ограничение по времени в 2 секунды способно выполнить только около 2 * 10 ^ 8 инструкций.

Строка N одинакова для всех запросов, и вы ищете только шаблон AC . Это означает, что вы можете предварительно вычислить таблицу поиска для ответов и избежать повторения через N для каждого запроса.

В таблице поиска будет указано количество вхождений AC с начала строки. Для ACACTACG это было бы

 A={0,1,1,2,2,2,3,3}
  

Это помогает, потому что «количество вхождений AC между x и y» совпадает с «количеством вхождений перед y, за исключением тех, которые находятся перед x». Подобные таблицы обычно полезны всякий раз, когда вам приходится отвечать на вопросы о диапазонах

Например, для ответа на запрос 3,7 вы вычисляете A[7]-A[3] = 3-1 = 2.

Как сказал Джони, вы можете создать lookupArr, подобный arr. Поскольку шаблон для сопоставления имеет длину 2, основная идея заключается в:

• Сначала создайте массив длиной n 1, все значения которого будут заполнены 0.
• Во-вторых, когда вы пытаетесь сопоставить шаблон AC в строке s, поэтому отметьте 1 в индексе C в arr, когда вы сопоставляете AC в строке.
• Таким образом, вы будете выполнять итерацию массива только один раз, прежде чем отвечать на любой запрос
• Для каждого запроса вы можете решить это за O (1) время, поскольку общее количество найденных шаблонов будет равно arr[r] - arr[l-1]
• Примечание, убедитесь, что вы ищете частичные перекрытия, как описано в приведенном ниже коде

Надеюсь, это поможет:

 // This program is created by Ishpreet Singh
#include <iostream>
#include <string>
using namespace std;

int main()
{
  int n, q, l, r;
  string s;
  cin >> n >> q;
  cin >> s;
  // The lookUp Arr
  int arr[n   1];
  arr[0] = arr[1] = 0;
  for (int i = 1; i < n; i  )
  {
    if (s.at(i - 1) == 'A' amp;amp; s.at(i) == 'C'){
      arr[i   1] = arr[i]   1;
    }
    else{
      arr[i   1] = arr[i];
    }
  }
  while (q--)
  {
    cin >> l >> r;
    int ans = arr[r] - arr[l - 1];
    // To Remove partial overlaps of AC, like s[l-1] = 'A' and s[l] = 'C'
    if (l > 1 amp;amp; arr[l] == arr[l - 1]   1){
      ans--;
    }
    cout << ans << endl;
  }
  return 0;
}
  

Таким образом, вы можете отвечать на запросы за O(1) время, поэтому общая сложность кода будет такой, O(Q) что он пройдет весь тестовый пример за 1 секунду.