简介:

串(String)—–零个或多个字符组成的有限序列
串的示意图

a="beijinghuanyingni"
b="beijinghuanying"
c="beijin"
d=""

子串:串中任意个连续的字符组成的子序列称为该串的子串。
比如上面的b是a的子串、c是a或者b的子串。
空串:零个字符的串。注意是”“而不是” “。空串是任意串的子串,任意串是其自身的子串。
串的抽象数据类型
ADT String{
数据对象: D={ai|ai∈CharacterSet,i=1,2,…,n,n≥0}
数据关系:R1={ <\ai-1,ai>|ai-1,ai-1,ai∈D,i=2,…,n}
StrAssign(T,*chars): 生成一个其值等于字符常量chars的串T.

      StrCopy(T,S):     串S存在,由S复制得到T.

      ClearString(S):    串S存在,将串清空.

      StringEmpty(S):    若串为空,返回true,否则返回false.

      StrLentgth(S) :    返回串S的元素个数,即串的长度.

      StrCompare(S,L):    比较S和T,若S>T,返回>0,S==T返回0,
      S

      SubString(Sub, S, pos, len): 串S存在,1<=pos<=StrLentgth(S),且 0<=len<=StrLentgth(S)-pos+1,用Sub返回串S的第pos个起

                     长度为len的子串.

      Index(S,T,pos)

      Replace(S,T,V)     串S,T,V存在,T是非空串,用V替换S中出现的所有与T相等的不重叠的子串.

      StrInsert(S,T,pos): 在串S的第pos个字符之前插入串T.

      StrDelete(S,pos,len): 从串S中删除第pos个字符起的长度为len的子串.
}
串的存储结构

  • 顺序存储
  • 链式存储
    顺序存储表示
    typedef struct{
    char *ch;//若串非空,则按照串长分配存储区,否则ch为NULL
    int length;//串长度
    }String;
    链式存储表示#define CHUNKSIZE 80
    typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk *next;
    }Chunk;
    typedef struct{
    Chunk *head,*tail;
    int curled;
    }String;
    链式存储优点:操作方便
    缺点:存储密度较低
    存储密度=串值所占的存储位/实际分配的存储位

BF算法
BF(Brute-Force)算法的基本思路:
1)从目标串s的第一个字符起和模式串的第一个字符进行比较,若相等。则继续逐个比较后续字符,否则从串s的第二个字符起再重新和串t进行比较。
2)依次类推,直至串t中的每个字符依次和串s的一个连续的字符序列相等,则模式匹配成功,此时串t的第一个字符在串s的位置就是t在s中的位置,否则模式匹配不成功。
BF算法匹配过程

#include <stdio.h>
#include "stdlib.h"
//宏定义
#define TRUE   1
#define FALSE   0
#define OK    1
#define ERROR   0
#define  MAXSTRLEN 100
typedef char    SString[MAXSTRLEN + 1];
//返回子串T在主串S中第pos位置之后的位置,若不存在,返回0
 int BFindex(SString S, SString T, int pos)
{
if (pos <1 ||  pos > S[0] ) exit(ERROR);
int i = pos, j =1;
while (i<= S[0] && j <= T[0])
{
    if (S[i] == T[j])
    {
        ++i; ++j;
    } else {
        i = i- j+ 2;
        j = 1;
    }
}
if(j > T[0]) return i - T[0];
return ERROR;
}
void main(){
SString S = {13,'a','b','a','b','c','a','b','c','a','c','b','a','b'};
SString T = {5,'a','b','c','a','c'};
int pos;
pos = BFindex( S,  T, 1);
printf("%d",pos);
}

BF算法特点:
通过上面的例子可以看到BF算法思路直接简明。但当匹配失败时,主串的指针i总是要回到i-j+2位置,模式串的指针总是恢复到首字符的位置j=1,因此,算法时间复杂度高。
KMP算法
KMP算法是改进了BF算法,小编对这个算法也是似懂非懂,今后学习后会为大家讲解

目录
相关文章
|
6月前
|
存储 算法 程序员
串是什么,串存储结构的3种实现方法
串是什么,串存储结构的3种实现方法
104 8
|
C语言
带你快速了解字符(串)函数(一)
带你快速了解字符(串)函数(一)
|
26天前
|
算法
串ababaaababaa的next和串ababaabab的nextval
本文介绍了计算字符串的next数组和nextval数组的方法,通过分析两个具体的例子来展示如何计算这些数组,这些数组通常用于KMP算法中。
71 0
串ababaaababaa的next和串ababaabab的nextval
|
3月前
|
C++
串应用- 计算一个串的最长的真前后缀
这篇文章提供了一个C++程序,用于找出给定字符串的最长真前后缀,并展示了如何通过计算每个子串的最长相同前后缀来实现这一功能。
带你快速了解字符(串)函数(二)
带你快速了解字符(串)函数(二)
带你快速了解字符(串)函数(三)
带你快速了解字符(串)函数(三)
|
6月前
leetcode-1545:找出第 N 个二进制字符串中的第 K 位
leetcode-1545:找出第 N 个二进制字符串中的第 K 位
33 0
|
6月前
leetcode-1784:检查二进制字符串字段
leetcode-1784:检查二进制字符串字段
31 0
|
6月前
|
开发框架 .NET C#
C# | [二进制字符串] 与 [字节数组] 互相转换,一行代码就搞定! - CodePlus系列
开发中有时需要将二进制数据转换为字符串或相反。虽然.NET提供了一些用于二进制数据操作的类库,但是它们的使用有时候会比较繁琐。STTech.CodePlus是一个.NET扩展库,它提供了很多实用的扩展方法,可以帮助我们更方便地进行二进制数据操作。 在本文中,我们将介绍如何使用STTech.CodePlus扩展库实现二进制字符串和字节数组的快速互相转换。
260 0
|
算法
【Day20】LeetCode算法题【1784. 检查二进制字符串字段】【14. 最长公共前缀】
了解LeetCode算法题【1784. 检查二进制字符串字段】。
114 0
【Day20】LeetCode算法题【1784. 检查二进制字符串字段】【14. 最长公共前缀】