Поиск подстроки, но не для всех входов?

Question

Я написал код для поиска индекса самой большой подстроки в большей строке.

Подстрока найдена, когда есть равное количество a и b.

Например, если дать 12 и bbbbabaababb, то получится 2 9, поскольку первая появляющаяся подстрока начинается с индекса 0 и заканчивается индексом 9. 3 10 также является ответом, но поскольку это не такпервая появившаяся подстрока, это не будет ответом.

Код, который я сделал:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

void substr(char str[], int n) {
    int sum = 0;
    int max = -1, start;

    for (int i = 0; i < n; i++) {
        if (str[i]=='a') {
            str[i] = 0;
        } else if(str[i]=='b') {
            str[i] = 1;
        }
    }

    // starting point i
    for (int i = 0; i < n - 1; i++) {
        sum = (str[i] == 0) ? -1 : 1;

        // all subarrays from i
        for (int j = i + 1; j < n; j++) {
            (str[j] == 0) ? (sum += -1) : (sum += 1);

            // sum == 0
            if (sum == 0 && max < j - i + 1 && n%2==0) {
                max = j - i + 1;
                start = i-1;
            } else if (sum == 0 && max < j - i + 1 && n%2!=0) {
                max = j - i + 1;
                start = i;
            }
        }
    }

    // no subarray
    if (max == -1) {
        printf("No such subarray\n");
    } else {
        printf("%d %d\n", start, (start + max - 1));
    }
}


/* driver code */
int main(int argc, char* v[]) {
    int n;              // stores the length of the input
    int i = 0;          // used as counter

    scanf("%d", &n);

    n += 1;         // deals with the /0 at the end of a str

    char str[n];    // stores the total

    /* adding new numbers */
    while(i < n) {
        char new;
        scanf("%c", &new);
        str[i] = new;
        ++i;
    }

    substr(str, n);

    return 0;
}

Он работает для многих значений, но не для второго примера (приведенного ниже). Он должен вывести 2 9, но даст 3 10. Это допустимая подстрока, но не первая ...

Пример входов и выходов должен быть:

Input      Input           Input
5          12              5
baababb    bbbbabaababb    bbbbb
Output     Output          Output
0 5        2 9             No such subarray

Answer 1

У вас есть несколько проблем, многие из которых связаны с размерами и индексами массивов.

• Когда вы читаете в массиве, вам нужно n символов. Затем вы увеличиваете n в oder для размещения нулевого терминатора. Хорошей идеей является завершение строки нулем, но '\0' в конце действительно не является частью строковых данных. Вместо этого настройте размер массива при создании массива и поместите нулевой терминатор явно:

  char str[n + 1];
  
  // scan n characters
  str[n] = '\0';
  

• В C (и других языках) диапазоны определяются включающей нижней границей,но исключительной верхней границей: [lo, hi). Верхняя граница hi не является частью диапазона, и в диапазоне есть hi - lo элементов. (Массивы с элементами n представляют собой особый случай, где допустимый диапазон равен [0, n).) Вы должны принять это соглашение, а не бороться с ним. Если ваш вывод должен быть другим, измените вывод, а не представление в вашей программе.

  (И даже как ваш первый пример, где вы должны иметь строку из пяти символов, на самом деле читает и учитывает b в 6-й позиции. Это явная ошибка.)

• Положение максимально допустимой подстроки не зависит от того, является ли общая длина строки нечетной или четной!

• Первый проход, где вы конвертируете все «a» и «b» в 0 и 1, не нужен, и он уничтожает исходную строку. Это не большая проблема, но помните об этом.

Реальная проблема заключается в том, как вы пытаетесь найти подстроки. Ваша идея добавить 1 для «a» и вычесть одну для «b» хороша, но вы не правильно храните свои суммы. Для каждой возможной начальной точки i вы сканируете остаток строки и ищите нулевую сумму. Это будет работать только в том случае, если вы сбросите сумму на ноль для каждого i.

void substr(char str[], int n)
{
    int max = 0;
    int start = -1;

    for (int i = 0; i + max < n; i++) {
        int sum = 0;

        for (int j = i; j < n; j++) {
            sum += (str[j] == 'a') ? -1 : 1;

            if (sum == 0 && max < j - i) {
                max = j - i;
                start = i;
            }
        }
    }

    if (max == 0) {
        printf("No such subarray\n");
    } else {
        printf("%d %d\n", start, start + max);
    }
}

Зачем инициализировать max = 0 вместо -1? Поскольку вы сначала добавляете + 1 / -1, ваша проверка никогда не найдет подстроку max == 0, но есть возможность оптимизации: если вы уже нашли длинную подстроку, вам не нужно смотреть на «хвост»вашей строки: Условие цикла i + max < n обрезает поиск.

(Есть и другая причина: обычно размеры и индексы представлены беззнаковыми типами, например, size_t. Если вы используете 0 какИсходное значение, ваш код будет работать для типов без знака.)

Алгоритм не самый эффективный для больших массивов, но он должен работать.