串

串

1.定义和基本操作

1.定义

1、串、即字符串，由零个或多个字符组成的有限序列。串中字符的个数n称为串的长度。n=0表示的串称为空串。如S = "hello world"，S为串名

2、子串，串中任意个连续的字符组成的子序列

3、主串：包含子串的串

4、字符在主串中的位置：字符在串中的序号（此处序号是位序）

5、子串在主串中的位置：子串第一个字符在主串中的位置

2.特点

1、串是一种特殊的线性表，数据元素之间呈线性关系

2、串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

3、串的基本操作，如增删改查等通常以子串为操作对象

2.串的基本操作

1.基本操作

//赋值操作。把T赋值给chars
StrAssign(&T, chars);
//复制操作。由串S复制得到串T
StrCopy(&T,S);
//判空操作。若S为空串，则返回true
StrEmpty(S);
//求串场
StrLength(S);
//清空串，变成空串
ClearString(&S);
//销毁串
DestroyString(&S);
//串连接
Concat(&T,S1,S2);
//截取子串
SubString(&Sub,S,pos,len);
//找到S中子串T的位置
Index(S,T);
//比较操作
StrCompare(S,T);

2.字符集编码

1、字符在计算机中以二进制的形式存储

2、常见的字符集方式有

1）ASCII字符集——英文字符

2）Unicode字符集——中英文字符

3、字符集编码

1）ASCII编码

2）Unicode编码

3）UTF-8编码

字符集编码，就是将字符集中的字符通过编码规则映射为计算机中的唯一二进制编码

4、乱码问题：

编码方式和解码方式不同的时候，会出现乱码的问题（如采用GBK编码，解码采用UTF-8时，会出现乱码现象）

3.串的存储结构

1.顺序存储

1.定义

//静态数组实现
#define MaxSize 255
typedef struct{
  char ch[MaxSize];
  int length;
}SString;


//童泰数组实现（堆分配存储）
typedef struct{
  char *ch;
  int length;
}HString;

//初始化
void InitHString(HString& S){
  S.ch = (char*)malloc(sizeof(char)*MaxSize);
  S.length = 0;
}
//销毁
void DestoryString(HString& s){
  if(S.ch != NULL){
    free(S.ch);
    S.ch = NULL;
  }
}

2.如下图所示

2.串的链式存储

1.定义

//方式一：缺点是存储密度低，每个字符1B，每个指针4B
typedef struct StringNode{
  char ch;
  struct StringNode *next;
}StringNode,*StringList;

//方式二：相对提高存储密度
typedef struct StringNode{
  char ch[4];
  struct StringNode *next;
}StringNode, *StringList;

4.基本操作实现

1.截取子串

//采用顺序存储实现
//串的第0位不存储字符
bool SubString(SString &Sub, SString S, int pos, int len){
  if(pos + len - 1 > S.length){
    return false;
  }
  for(int i = pos; i < pos + len; i++){
    Sub.ch[i-pos + 1] = S.ch[i];
  }
  Sub.length = len;
  return true;
}

2.比较两个串的大小

int StrCompare(SString S, SString T){
  for(int i = 1; i <= S.length && i <= T.length; i++){
    if(S.ch[i] != T.ch[i]){
      return S.ch[i] - T.ch[i];
    }
  }
  //所有字符相同，比较长度
  return S.length - T.length;
}

3.在主串中找子串

int Index(SString S, SString T){
  int i = 1, n = S.length, m = T.length;
  SString sub;        //用于暂存子串
  while(i <= n - m + 1){
    //先截取
    SubString(sub, S, i, m);
    //再比较
    if(StrCompare(sub,T) != 0) ++i;
    else return i;
  }
  //S中不存在与T相等的子串
  return -1;
}

5.模式匹配

//主串
S = "Hello world";
//子串
s1 = "Hello";
s2 = "world";
s3 = "llo";
//模式串
p1 = "ll"

1.定义

1、串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在的位置

2、子串：一定是主串中存在俄才叫“子串”

3、模式串：主串中未必存在的串

2.朴素模式匹配算法

暴力搜索

//实现第一个位置不存储字符
int Index(SString S, SString T){
  //int k = 1;
  int i = k, j = 1;
  while(i <= S.length && j <= T.length){
    if(S.ch[i] == T.ch[j]){
      ++i;
      ++j;
    }
    else{
      //k++;
      //i = k;
      i = i - j + 2;
      j = 1;
    }
  }

  if(j > T.length){
    //匹配成功
    //return k;
    return i - T.length;
  }
  else{
    //匹配失败
    return 0;
  }
}

1、若模式串长度为m，主串长度n，则：

1）匹配成功最好的时间复杂度为O(m)

2）匹配失败的最好的时间复杂度为O(n -m + 1) = O(n - m ) = O(n)；（此时每次匹配到模式串第一个字符就匹配失败）

3）匹配失败的最坏时间复杂度为 O(nm)（此时每次匹配到模式串的最后一个字符才匹配失败，因此每次需要回溯，匹配的次数是 (n-m+1)*m 次）

6.KMP算法

朴素模式匹配算法的优化

1.思想

int Index_KMP(SString S, SString T, int next[]){
  int i = 1, j = 1;
  while(i <= S.length && j <= T.length){
    if(j == 0 || S.ch[i] = T.ch[j]){
      //继续比较后继的字符,匹配失败后j = 0，i需要指向下一个字符
      ++i;
      ++j;            
    }
    else{
      //模式串向右移动
      j = next[j];
    }
  }
  if(j > T.length)
    return i - T.length;        //匹配成功，返回首字符的下标
  else
    return 0;
}

2.next[]数组

1.手算

串的前缀：包含第一个字符，且不包含最后一个字符的子串

串的后缀：包含最后一个字符，且不包含第一个字符的子串

当第j个字符匹配失败，由前1~j-1个字符组成的串记为S，则：

next[j] = S的最长前后缀长度 + 1

//特别的
next[1] = 0;

2.例子

模式串“ababaa”

next[j] = S的最长前后缀长度 + 1

模式串“aaaab"

3.next代码实现

//求模式串T的next数组
int next[T.length + 1];

void get_next(SString T, int next[]){
  int i = 1, j = 0;
  next[1] = 0;
  while(i < T.length){
    if(j == 0 || T.ch[i] == T.ch[j]){
      //若pi = pj,则 next[j + 1] = next[j] + 1
      ++i;
      ++j;
      next[i] = j;
    }
    else{
      j = next[j];
    }
  }
}

3.算法分析

1.时间复杂度

当子串和模式串不匹配时，主串指针i不回溯，算法平均时间复杂度为O(m+n)

2.算法优化

继续优化next数组，避免不必要的重复匹配，用nextval数组代替next数组