【数据结构】字符串之字符串的基本操作和BF(Brute-Forc

字符串定义

【定义】：串(String)是由零个或多个字符组成的有限序列，又叫字符串。

相关概念

• 空格串：只包含空格的串。注意它与空串的区分，空格串是有内容有长度的，而且可以不止一个空格。
• 子串与主串：串中任意个数的连续字符组成的子序列成为该串的子串，包含子串的串成为主串。（比如over是lover的子串，lover是over的主串）
• 子串在主串中的位置就是子串的第一个字符在主串中的序号。

---

串的存储结构

串的存储结构和线性表相同，分为顺序存储和链式存储。

串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般使用定长数组来表示。
特点：

• 一般可以将实际的串长度值保存在数组的0下标位置。比如串T，那么可以将T[0] = 串的长度来存放。串的长度可以通过C语言里面的strlen函数获取。
• 为解决预定义的存储空间不足问题，串的存储空间可以在执行程序过程中分配而得。比如在计算机中存在一个自由存储区-堆。这个堆可以由C语言中的动态分配函数malloc()和free()来管理。

串的链式存储结构

串的链式存储结构除了在连接串和串操作时有一定的方便之外，都不如顺序存储灵活，性能也不如顺序存储结构好所以很少用。

---

串的基本操作

串的基本操作包括输出字符串、判断字符串是为空、获取字符串中元素的个数清空字符串等。这些都比较简单和基本，直接上代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE  40 //存储空间初始分配量

typedef int  Status;
typedef int  ElemType;

typedef char String[MAXSIZE +1];

/**
 * 输出字符串
 */
void StrPrint(String T){
    
    int i;
    for (i = 1; i <= T[0]; i++)
        printf("%c", T[i]);
    printf("\n");
}

/**
 * 生成一个其值等于chars的字符串T
 */
Status StrAssign(String T, char * chars){
    
    int i;
    
    if (strlen(chars) > MAXSIZE)
        return ERROR;
    else{
        T[0] = strlen(chars);
        for (i = 1; i <= T[0]; i++) {
            T[i] = *(chars + i - 1);
        }
        return OK;
    }
        
}

/**
 * 由字符串S复制得字符串T
 */
Status StrCopy(String T, String S){
    int i;
    for (i = 0; i <= S[0]; i++) {
        T[i] = S[i];
    }
    return OK;
}

/**
 *判断字符串S是否为空
 */
Status StrEmpty(String S){
    if (S[0] == 0)
        return TRUE;
    else
        return FALSE;
}

/**
 * 比较两个字符串的大小
 * 操作结果：如果S>T，则返回值>0;若S=T,则返回值=0;若S<T，则返回值<0
 */
int StrCompare(String S, String T){
    int i;
    for (i = 1; i<=S[0]&&i<=T[0]; i++) {
        if (S[i] != T[i])
            return S[i] - T[i];
    }
    return S[0] - T[0];
}

/**
 * 获取字符串的元素个数
 */
int StrLength(String S){
    return S[0];
}

/**
 * 清空一个字符串
 */
Status ClearString(String S){
    if (S)
        S[0] = 0; // 令字符串长度为0
    return OK;
}

/**
 * 合并两个字符串
 * T为合并S1和S2后的结果
 */
Status Concat(String T, String S1, String S2){

    int i;
    if (S1[0]+S2[0] <= MAXSIZE) {
        
        for (i = 1; i <= S1[0]; i++)
            T[i] = S1[i];
        for (i = 1; i <= S2[0]; i++)
            T[S1[0]+i] = S2[i];
        
        T[0] = S1[0] + S2[0];
        
        return TRUE;
        
    }else{ // S1+S2 的字符串长度大于了存储空间
        
        for (i = 1; i <= S1[0]; i++)
            T[i] = S1[i];
        for (i = 1; i <= S2[0]; i++)
            T[S1[0] + i] = S2[i];
        
        T[0] = MAXSIZE;
        
        return FALSE;
    }
}

/**
 * 截取第pos个字符起长度为len的子串
 */
Status SubString(String Sub, String S, int pos, int len){
    
    int i;
    if (pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1 ) // 不在范围内
        return ERROR;
    
    for (i = 1; i <= len; i++)
        Sub[i] = S[pos + i - 1];
    
    Sub[0] = len;
    
    return OK;
}

/**
 *字符串中S插入字符串T
 */
Status StrInsert(String S, int pos, String T){
    
    int i;
    if (pos < 1 || pos > S[0] + 1)
        return ERROR;
    
    if (S[0] + T[0] <= MAXSIZE) { // 完全插入
        
        for (i = S[0]; i >= pos; i--)
            S[i + T[0]] = S[i];
        for (i = pos; i < pos + T[0]; i++)
            S[i] = T[i - pos + 1];
        
        S[0] += T[0];
        
        return TRUE;
    }else{   // 部分插入
        for (i = MAXSIZE; i <= pos; i--)
            S[i + T[0]] = S[i];
        for (i = pos; i < pos + T[0]; i++)
            S[i] = T[i - pos + 1];
        
        S[0] = MAXSIZE;
        
        return FALSE;
    }
}

/**
 * 删除子串
 */
Status StrDelete(String S, int pos, int len){
    
    int i;
    if (pos < 1 || pos > S[0] - len + 1 || len < 0)
        return ERROR;
    
    for (i = pos+len; i <= S[0]; i++)
        S[i-len] = S[i];
    
    S[0] -= len;
    
    return OK;
}

---

BF(Brute-Force)算法

• BF算法是一种比较普通比较暴力的模式匹配算法。
• 所谓模式匹配，即子串的定位操作。这也是串中最重要的操作之一。
• BF算法适用于在处理简单的数据时候，完全匹配，速度慢。

BF的基本思想

• 从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s的第二个字符起再重新和串t进行比较。
• 依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。
• 算法的时间复杂度为O(n*m) ，n和m分别为主串和模式串的长度。

BF的匹配步骤详解

举个🌰：主串S = “goodGoogle”。找到T = “google”这个子串的位置。

• 1.主串S第一位开始，S与T前三个字母都匹配成功，但是S的第四个字母是d而T的是g.第一位匹配失败。

  
  

• 2.主串S第二位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败。

  
  

• 3.主串S第三位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败。

  
  

• 4.主串S第四位开始，主串S首字母是d，要匹配的T首字母是g，匹配失败。

  
  

• 5.主串S第五位开始，S与T，6个字母全部匹配，匹配成功。

  
  

代码：

/**
 * BF算法
 * 返回子串T在主串中的位置。若不存在，则函数返回值为-1
 */
int BFIndex(String S, String T)
{
    int i = 0; // i用于主串S中当前位置下标，
    int j = 0;  // j用于子串T中当前位置下标值
    
    while (S[i] && T[j])
    {
        
        if (S[i] == T[j])   // 两字母相等则继续
        {
            i++,j++;
        } else {     // 指针后退重新开始匹配
            i = i - j + 1; // i回退到上次匹配首位的下一位
            j = 0; // j回退到字符串T的首位
        }
    }
    
    if (j == strlen(T))
        return i - (int)strlen(T);
    else
        return  -1;
}

测试

int main(int argc, const char * argv[]){
    String s = "abcabcabcdabdabd";
    String t = "abd";
    printf("主串为：%s\n子串为：%s\n", s, t);
    printf("index = %d\n", BFIndex(s, t));
    return 0;
}