【9】数据结构的串篇章

串的定义

• 定义：由0个或多个字符组成的有限序列，由一对双引号引起来。记为"S"

顺序串的实现

初始化

    def __init__(self):
        """
        串初始化
        """
        self.str = list()
        self.length = ()

赋值

    def strAssign(self, string):
        """
        赋值
        :param string: 待赋值的串
        :return:
        """
        # 计算串的长度
        length = len(string)
        # 赋值
        self.str = list()
        for i in range(length):
            self.str.append(string[i])
        # 设置串的长度
        self.length = length

打印串

    def display(self):
        """
        打印
        :return:
        """
        print('当前串的长度：', end='')
        for i in range(self.length):
            print(self.str[i], end='')
        print()

求串的长度

    def getLength(self):
        """
        求串的长度
        :return: 串的长度
        """
        return self.length

复制串

    def strCopy(self, string):
        """
        复制串
        :param string: 待复制的串
        :return:
        """
        # 将当前串初始化
        self.str = list()
        # 循环复制
        for char in string.str:
            self.str.append(char)
        # 设置当前串的长度
        self.length = string.getLength()

判断两个串长度是否相等

    def strEquals(self, string):
        """
        判断两个串是否相等
        :param string: 待判定是否相等的串
        :return: 是否相等 true or false
        """
        if self.length == string.getLength():
            # 循环，逐一比较
            for i in range(self.length):
                if self.str[i] != string.str[i]:
                    break
            # 判断，如果i等于串的长度，则相等：否则不相等
            i += 1
            if i == self.length:
                return True
            else:
                return False
        else:
            return False

连接两个串

    def strConnect(self, string2):
        """
        连接两个串
        
        :param string2: 串2
        :return:
        """
        # 生成新串，并初始化
        newString = String()
        # 循环
        for i in range(self.length):
            newString.str.append(self.str[i])

        # 循环
        for i in range(string2.getLength()):
            newString.str.append(string2.str[i])
        # 设置串的长度
        newString.length = self.length + string2.getLength()
        return newString

比较两个串内容是否相等

    def strCompete(self, string):
        """
        两个串比较大小
        :param string: 带比较大小的串
        :return: 1为大于，0为等于，-1为小于
        """
        # 循环，逐个比较两个串相应位置的字符大小
        index = 0
        while index < self.length and index < string.getLength():
            if self.str[index] > string.str[index]:
                return 1
            elif self.str[index] < string.str[index]:
                return -1
            index += 1

        # 判断两个串是否还有字符，还存在字符的串大
        if index < self.length:
            return 1
        elif index < string.getLength():
            return -1
        else:
            return 0

插入操作

    def insert(self, offset, string):
        """
        插入
        :param offset: 插入位置
        :param string:
        :return:
        """
        # 判断位置是否正确
        if offset < 0 or offset > self.length:
            print("插入位置不合法！")
            return
        # 备份当前串
        temp = self.str
        # 初始化串
        self.str = list()
        for i in range(offset):
            self.str.append(temp[i])
        # 将待插入的串存入当前串
        for i in range(string.getLength()):
            self.str.append(string.str[i])
        # 将目标串剩余字符存入当前串
        for i in range(offset, self.length):
            self.str.append(temp[i])
        # 设置串的长度
        self.length = self.length + string.getLength()

删除操作

    def delete(self, offset, len):
        """
        删除
        :param offset: 删除开始位置
        :param len: 删除长度
        :return:
        """
        # 判断位置与长度是否合法
        if offset < 0 or offset > self.length or len > self.length - offset:
            print('删除位置不合法！')
            return
        # 备份当前串
        temp = self.str
        # 初始化串
        self.str = list()
        for i in range(offset):
            self.str.append(temp[i])
        # 将目标串剩余的字符存入当前串
        for i in range(offset + len, self.length):
            self.str.append(temp[i])
        # 设置串的长度
        self.length = self.length - len

调试与代码合集

class String:
    """
    串的定义
    """
    def __init__(self):
        """
        串初始化
        """
        self.str = list()
        self.length = ()

    def strAssign(self, string):
        """
        赋值
        :param string: 待赋值的串
        :return:
        """
        # 计算串的长度
        length = len(string)
        # 赋值
        self.str = list()
        for i in range(length):
            self.str.append(string[i])
        # 设置串的长度
        self.length = length

    def display(self):
        """
        打印
        :return:
        """
        print('当前串的长度：', end='')
        for i in range(self.length):
            print(self.str[i], end='')
        print()

    def getLength(self):
        """
        求串的长度
        :return: 串的长度
        """
        return self.length

    def strCopy(self, string):
        """
        复制串
        :param string: 待复制的串
        :return:
        """
        # 将当前串初始化
        self.str = list()
        # 循环复制
        for char in string.str:
            self.str.append(char)
        # 设置当前串的长度
        self.length = string.getLength()

    def strEquals(self, string):
        """
        判断两个串是否相等
        :param string: 待判定是否相等的串
        :return: 是否相等 true or false
        """
        if self.length == string.getLength():
            # 循环，逐一比较
            for i in range(self.length):
                if self.str[i] != string.str[i]:
                    break
            # 判断，如果i等于串的长度，则相等：否则不相等
            i += 1
            if i == self.length:
                return True
            else:
                return False
        else:
            return False

    def strConnect(self, string2):
        """
        连接两个串

        :param string2: 串2
        :return:
        """
        # 生成新串，并初始化
        newString = String()
        # 循环
        for i in range(self.length):
            newString.str.append(self.str[i])

        # 循环
        for i in range(string2.getLength()):
            newString.str.append(string2.str[i])
        # 设置串的长度
        newString.length = self.length + string2.getLength()
        return newString

    def strCompete(self, string):
        """
        两个串比较大小
        :param string: 带比较大小的串
        :return: 1为大于，0为等于，-1为小于
        """
        # 循环，逐个比较两个串相应位置的字符大小
        index = 0
        while index < self.length and index < string.getLength():
            if self.str[index] > string.str[index]:
                return 1
            elif self.str[index] < string.str[index]:
                return -1
            index += 1

        # 判断两个串是否还有字符，还存在字符的串大
        if index < self.length:
            return 1
        elif index < string.getLength():
            return -1
        else:
            return 0

    def insert(self, offset, string):
        """
        插入
        :param offset: 插入位置
        :param string:
        :return:
        """
        # 判断位置是否正确
        if offset < 0 or offset > self.length:
            print("插入位置不合法！")
            return
        # 备份当前串
        temp = self.str
        # 初始化串
        self.str = list()
        for i in range(offset):
            self.str.append(temp[i])
        # 将待插入的串存入当前串
        for i in range(string.getLength()):
            self.str.append(string.str[i])
        # 将目标串剩余字符存入当前串
        for i in range(offset, self.length):
            self.str.append(temp[i])
        # 设置串的长度
        self.length = self.length + string.getLength()

    def delete(self, offset, len):
        """
        删除
        :param offset: 删除开始位置
        :param len: 删除长度
        :return:
        """
        # 判断位置与长度是否合法
        if offset < 0 or offset > self.length or len > self.length - offset:
            print('删除位置不合法！')
            return
        # 备份当前串
        temp = self.str
        # 初始化串
        self.str = list()
        for i in range(offset):
            self.str.append(temp[i])
        # 将目标串剩余的字符存入当前串
        for i in range(offset + len, self.length):
            self.str.append(temp[i])
        # 设置串的长度
        self.length = self.length - len

if __name__ == '__main__':
	# 16.串
    string1 = String()
    str = input('请输入你的第1个串的内容：')
    string1.strAssign(str)
    string1.display()
    print(f"当前string1串的长度为:{string1.getLength()}")
    # 复制
    string2 = String()
    str = input('请输入你的第2个串的内容：')
    string2.strAssign(str)
    string2.display()
    print(f"当前string2串的长度为:{string2.getLength()}")
    # string1.strCopy(string2)
    string1.display()
    print(f"当前string1串的长度为:{string1.getLength()}")
    # 判断是否相等串
    result = string1.strEquals(string2)
    if result:
        print('两个串相等')
    else:
        print('两个串不相等')
    # 连接两个串
    string3 = string1.strConnect(string2)
    string3.display()
    print(f"当前string3串的长度为:{string3.length}")
    # 两个串比较大小
    result = string1.strCompete(string2)
    if result == 1:
        print('string1 大于 string2')
    elif result == -1:
        print("string1 小于 string2")
    else:
        print('string1 等于 string2')
    # 插入
    string1.insert(3, string2)
    string1.display()
    print(f"当前string1的长度为:{string1.length}")
    # 删除
    string1.delete(3, 2)
    string1.display()
    print(f"当前string1的长度为:{string1.length}")

串的模式匹配算法

朴素的模式匹配算法

• 核心思路
  • 也称为暴力搜索算法。
  • 从目标串S的第一个字符开始与模式串P的第一个字符进行匹配
  • 如果匹配，继续逐个匹配后续字符，
  • 如果不匹配，模式串P返回到第一个字符，与目标串S的第二个字符进行匹配，
  • 如果匹配，继续逐个匹配后续字符，
  • 如果不匹配，模式串P返回到第一个字符，与目标串S的第三个字符进行匹配，
  • 以此类推…
• 最好情况：从第一个字符开始就匹配成功，模式串数量m，则时间复杂度为O(m)
• 最坏情况：没有匹配成功，每次匹配比较m次，共匹配n-m+1次，时间复杂度为O(n×m).
• 代码实现

def bruteForce(string1, string2):
    """
    暴力模式匹配
    :param string2:
    :return:
    """
    i = 0
    j = 0
    while i < len(string1) and j < len(string2):
        if string1[i] == string2[j]:
            j += 1
            i += 1
        else:
            i = i-j+1
            j = 0
    # 如果找到返回索引
    if j == len(string2):
        index = i - len(string2)
    # 否则返回-1
    else:
        index = -1
    return index

if __name__ == '__main__':
	string1 = "ababdabcd"
    string2 = "abc"
    print(bruteForce(string1, string2) + 1)

KMP算法实现模式匹配

• 核心思路

  • next列表的设计与生成。

  • 使用前后缀列表的方式去解析next值的设定

  • 其中：

    • 前缀列表表示除去最后一个字符后的前面所有子串组成的集合；
    • 后缀列表表示除去第一个字符后的后面所有子串组成的集合。

  • 以“abcabd”为例，求的next列表

  • 1.串‘a’的前缀和后缀均为空集，最长共有元素长度为0，

  • 2.串“ab”的前缀为{“a”}，后缀集合为{‘b’}，没有相同的前后缀的子串，最长共有元素长度为0，

  • 3.串“abc”的前缀集合为{“a”，“ab”}，后缀为{“c”，“bc”}，没有相同的前后缀的子串，最长共有元素长度为0，

  • 4.串“abca”的前缀集合为{“a”，“ab”，“abc”}，后缀为{“a”，“ca”，“bca”}，相同的前后缀子串为“a”，最长共有元素长度为1，

  • 5.串“abcab”的前缀集合为{“a”，“ab”，“abc”，“abca”}，后缀为{“b”，“ab”，“cab”，“bcab”}，相同的前后缀子串为“ab”，最长共有元素长度为2，

  • 6.串“abcabd”的前缀集合为{“a”，“ab”，“abc”，“abca”，“abcab”}，后缀为{“d”，“bd”，“abd”，“cabd”，“bcabd”}，没有相同的前后缀子串，最长共有元素长度为0，

  • 7.最后得出字符串“abcabd”的next列表为[-1,0,0,0,1,2].

• 代码实现

def createNext(pattern):
    length = len(pattern)
    # 定义next列表
    next = [0 for _ in range(len(pattern))]
    next[0] = -1
    next[1] = 0
    # 计算next列表
    k = -1
    j = 0
    while j < length-1:
        if pattern[k] == pattern[j] or k == -1:
            j += 1
            k += 1
            next[j] = k
        else:
            k = next[k]
    print(next)
    return next

def kmpSearch(text, pattern):
    # 得到next列表
    next = createNext(pattern)
    # 匹配字符串
    i = 0
    j = 0
    while i < len(text) and j < len(pattern):
        if text[i] == pattern[j] or j == -1:
            i += 1
            j += 1
        else:
            j = next[j]
    if j >= len(pattern):
        return True
    else:
        return False

if __name__ == '__main__':
	text = "ababdabcabcabd"
    pattern = "abcabd"
    print(kmpSearch(text, pattern))