[开发工具]KMP算法C++实现中内存异常

KMP算法C++实现中内存异常

代码

#include <string.h>

#include <iostream>
using namespace std;

typedef struct {
  char* ch;
  int length;
} SString;

int KMP(SString S, SString T, int next[]) {
  int i = 0, j = -1;
  while (i < S.length && j < T.length) {
    if (j == -1 || S.ch[i] == T.ch[j]) {
      ++i;
      ++j;
    } else
      j = next[j];
  }
  if (j >= T.length)
    return i - T.length;
  else
    return 0;
}

void getnext(SString T, int next[]) {
  int i = 0, j = -1;
  next[0] = -1;
  while (i < T.length) {
    if (j == -1 || T.ch[i] == T.ch[j]) {
      ++i;
      ++j;
      next[i] = j;
    } else
      j = next[j];
  }
}

int main() {
  SString S, T;
  S.ch = "abaabbababbab";
  S.length = strlen(S.ch);
  T.ch = "ababb";
  T.length = strlen(T.ch);
  int next[T.length];
  getnext(T, next);
  int result = KMP(S, T, next);
  printf("%d\n", result);
  return 0;
}

问题

在末尾的main函数中定义next数组时，可以看到长度使用了T.length。这时候在VS2019里会报错，因为VS2019不支持用变量定义数组长。而VSCode和CodeBlocks中可以正常运行并输出正常结果，通过查看变量地址T并没有改变。但是！！！若直接定义int next[5],则VS2019、VSCode和CodeBlocks会报相同的错误：在KMP中while执行对T访问时非法，进一步调试发现，T.ch在getnext执行后地址居然变成了0x0，且内容也为空(也有可能0x0处为系统保护区)，这样在KMP进行调用时无法访问造成异常。个人一直不明白为什么T.ch会变…