Уменьшить количество вложенных циклов

Question

Ниже приведен код, где я должен проверить определенный символ в подстроке строки.Как я могу уменьшить его сложность, так как я использую три for цикла, но хочу сделать это в два или один цикл?

int main(void) {
    int i, j, k, t, n;
    scanf("%d", &t);
    while (t--) {
        int count = 0;
        scanf("%d", &n);
        char a[n], ch;
        scanf("%s %c", a, &ch);
        for (i = 0; i < n; i++) {
            for (j = i; j < n; j++) {
                for (k = i; k <= j; k++) {
                    if (a[k] == ch) {
                        count++;
                        break;
                    }
                }
            }
        }
        printf("%d", count);
    }
}

Answer 1

Вы можете использовать memchr вместо самого внутреннего цикла.

Заменитель

            for (k = i; k <= j; k++) {
                if (a[k] == ch) {
                    count++;
                    break;
                }
            }

для

  if (memchr(&a[i], ch, j - i + 1) != NULL) {
      count++;
  }

Это заставит вас использовать два цикла в вашем коде.

Answer 2

Итак, как вы видите из своего кода, вы пытаетесь сгенерировать набор подстрок, поэтому, если ваш массив был abc, то подстроки были бы a, ab, abc, b, bc, c.Затем вы пытаетесь посчитать, сколько раз символ появляется, так что если ch = 'b', то результат будет 4. Итак, вы подсчитываете количество строк, содержащих ch.

Так что один из способов решения этой проблемыс меньшим количеством циклов будет распознавать для каждого значения i, вы создаете строки, добавляя символ в последнюю строку, и если предыдущая строка содержала n копий ch, то следующая строка содержит n илиn+1 копирует в зависимости от фактического значения.

Еще один возможный подход для перехода к одному циклу - цикл по массиву один раз, и каждый раз, когда вы обнаружите, что символ ch вычисляет, сколько подстрок будетсодержать символ в этой позиции.Таким образом, для abc примера 2 из 3 строк, начинающихся в позиции 0, и 2 строк, начинающихся в позиции 1, будет содержать значение.