字符串

  • 串：字符串，有零个或者多个字符组成的有限序列
  • 串长：串中字符的个数
  • 空串：零个字符的串
  • 子串：串中任意个连续字符组成的子序列。原串称为主串

字符串的存储可以使用顺序存储和链式存储两种方式。

顺序存储

用一段连续的空间存储字符串。可以预先分配一个固定长度Maxsize的空间在这个空间中存储字符串。

  1. 以**’\0’**表示字符串的结束（C/C++、Java）。
  2. 在0空间存储字符串的长度。下标0的空间不使用，因此可以预先分配Maxsize+1的空间，在下标为0的空间存储字符串长度。

Screenshot_20200812_123644

  1. 结构体变量存储字符串长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct Str {
  // 存储数组
  char ch[Maxsize];
  // 字符串的长度
  int length;
}

// 或
typedef struct Str {
  // 字符串指针
  char *ch;
  // 字符串的长度
  int length;
}

链式存储

顺序存储的串在插入和删除操作时，需要移动大量元素，因此也可以采用链表的形式存储。

Screenshot_20200812_124058

模式匹配

子串的定位运算称为串的模式匹配或串匹配。

BF算法

暴力匹配

  1. 最好情况：每一次都在第一次比较时发现不等，最好情况下的平均时间复杂度为$O(n+m)$

  2. 最坏情况：每一次都匹配到T的最后一个字符发现不等。回退重新开始。最坏情况下的平均时间复杂度为$O(m*n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>

int bf(char *s, char *t) {
  int index = 0, i = 0, j = 0;
  while(s[i] != '\0' && t[j] != '\0') {
    if(s[i] == t[j]) {
      i ++;
      j ++;
    } else {
      index ++;
      i = index;
      j = 0;
    }
  }
  if(t[j] == '\0') {
    return index;
  }
  return -1;
}

int main(int argc, char *argv[])
{
  char *s = "asssasdfasdf";
  char *t = "sdf";
  printf("index = %d\n", bf(s, t));
  return 0;
}

KMP算法

KMP的核心在于回退的位置，回退时保证前面的字符相等，也就是求最大相同的前缀和后缀。

部分匹配表（PMT, Partial Match Table），如匹配的字符如下：

char index pmt next
a 0 0 -1
b 1 0 0
a 2 1 0
b 3 2 1
a 4 3 2
b 5 4 3
c 6 0 4
a 7 1 0
  1. index为1时，a!=b，则pmt=0，next也回溯到下标0
  2. index为2时，存在a=a，而ab!=ba，所以pmt=1，next也回溯到a的下标0的位置
  3. index为3时，存在ab=ab，所以pmt为2，当匹配到ababa，时最后一个a不相等时即可回溯到下标为1的位置，因为前面的ab都相等。
  4. …

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int* getNext(char *t) {
  int len = strlen(t);
  int *next = (int*) malloc(sizeof(int) * len);
  int i = 0, j = -1;
  next[0] = -1;
  while(i < len) {
    if(j == -1 || t[i] == t[j]) {
      i ++;
      j ++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
  return next;
}

int kmp(char *s, char *t) {
  int *next = getNext(t);
  printf("the next array is : [");
  for (int i = 0; i < strlen(t); ++i) {
    printf("%d ", next[i]);
  }
  printf("]\n");

  int i = 0, j = 0;
  int slen = strlen(s);
  int tlen = strlen(t);
  while(i < slen && j < tlen) {
    if(j == -1 || s[i] == t[j]) {
      i ++;
      j ++;
    } else {
      j = next[j];
    }
  }
  free(next);
  
  if(j == tlen) {
    return i-j;
  }
  return -1;
}

int main(int argc, char *argv[])
{
  char *t = "abababca";
  char *s = "1231saabababca1asdf";
  int r = kmp(s, t);
  printf("result is : %d\n", r);
  return 0;
}