c - 查找子字符串，但不是所有输入？

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为了容纳空终止符。以空值终止字符串是个好主意，但是 '\0'最后确实不是字符串数据的一部分。相反，请在创建数组时调整数组大小并显式放置空终止符:

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

• 在 C(和其他语言)中，范围由包含下界和排除上限定义: [lo, hi) 。上限hi不属于该范围，有 hi - lo范围内的元素。 (带有 n 元素的数组是一种特殊情况，其有效范围是 [0, n) 。)您应该接受而不是反对这个约定。如果您的输出应该不同，请修改输出，而不是程序中的表示。

  (而不是你的第一个示例，你应该有一个由五个字符组成的字符串，实际上如何读取并考虑第六个位置的 b。这是一个明显的错误。)

• 最大有效子串的位置并不取决于整个字符串长度是奇数还是偶数!

• 第一遍将所有“a”和“b”转换为 0 和 1 是不必要的，它会破坏原始字符串。这不是一个大问题，但请记住这一点。

实际的问题是如何找到子字符串。您为“a”加 1 并为“b”减 1 的想法很好，但您没有正确保存总和。对于每个可能的起点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 作为初始值，您的代码将适用于无符号类型。)

该算法对于大型数组来说并不是最有效的，但它应该可以工作。