串/字符串(String)是一种特殊的线性表，其数据元素为字符。串是仅由字符串构成的有限序列，是取值范围受限的线性表。一般记作S=’a1a2···an‘，其中S是串名，单引号括起来的字符序列是串值。

基本概念

  • 空串：长度为零的串，空串不包含任何字符。
  • 空格串：由一个或多个空格组成的串。空格字符也是一个字符。
  • 子串：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。空串是任意串的子串。
  • 串相等：两个串的长度且对应位置上的字符都相等。

基本操作

  • 赋值操作Assign(s, t): 将串s的值赋给串t。
  • 联接操作Concat(s, t): 将串t联接到串s的末端，形成新串。
  • 求串长StrLengh(s): 返回串s的长度。
  • 求子串SubString(s, start, len): 返回串s中从start开始的、长度为len的字符序列。

匹配算法

朴素/BF模式匹配算法

主要思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐对字符进行后续的比较，否则从主串第二个字符起与模式串的第一个字符串重新比较，直到模式串中的每个字符依次和主串中的一个连续的字符序列相等为止，此时称为匹配成功。如果不能在主串中找到与模式串相同的字串，则匹配失败。

//========================================
// 返回模式串在主串中的位置，否则返回-1
//========================================
int Index(char S[], char T[], int pos) {
  int i, j, slen, tlen;
  i = pos;
  j = 0;
  slen = strlen(S);
  tlen = strlen(T);
  while(i < slen && j < tlen) {
    if (S[i] == T[j]) { i++; j++; }
    else { i = i - j + 1; j = 0; }
  }
  if (j >= tlen) return i - tlen;
  return -1;
}

KMP模式匹配算法

与朴素模式匹配算法相比较：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的部分匹配结果向右移动，再继续进行比较。 部分匹配表：又称失配函数，作用是让算法无需多次匹配S中的任何字符。能够实现线性时间搜索的关键是在主串的一些字段中检查模式串的出初始字段，我们可以确切地知道在当前位置之前的一个潜在匹配位置。

//======================
// 模式串中的next函数
//======================
void next（char *p, int next[]) {
  int i = 0, j = -1, slen;
  slen = strlen(p);
  next[0] = -1;
  while(i < slen) {
    if(j == -1 || p[i] == p[j]) {
      ++i; ++j; next[i] = j;
    } else {
      j = next[j]
    }
  }
}

//==============================================================
// KMP模式匹配算法
// input: s为主串，p为模式串，pos为开始匹配的位置，next为数组
// output: 匹配成功，返回模式串在主串中的位置，否则返回-1
//===============================================================
int KMP(char *s, char *p, int pos, int next[]) {
  int i, j, slen, plen;
  i = pos - 1;
  j = -1;
  slen = strlen(s);
  plen = strlen(p);
  while(i < slen && j < plen) {
    if (j == -1 || s[i] == p[j]) {
      ++i; j++;
    } else {
      j = next[j];
    }
  }
  if(j >= plen) return i - plen;
  else return -1;
}