数据结构 串的定位代码

在计算机科学中，数据结构中的串通常是指一连串字符组成的序列，例如字符串。对于查找特定字符或子串在串中的位置，常用到的是字符串匹配算法，如朴素的线性搜索、KMP算法、Boyer-Moore算法或Rabin-Karp算法等。

**线性搜索法 (简单查找)**：

def linear_search(s, target):
    for i in range(len(s)):
        if s[i] == target:
            return i
    return -1  # 如果没有找到目标，返回-1表示不存在

s = "hello world"
target = "world"
position = linear_search(s, target)

**KMP算法 (一种改进的线性搜索)**
KMP算法通过预处理模式串构建一个部分匹配表，用于跳过不必要的比较，提高效率。

from collections import deque

def build_prefix_table(pattern):
    table = [0]
    j = -1
    for i in range(1, len(pattern)):
        while j != -1 and pattern[j + 1] != pattern[i]:
            j = table[j]
        if pattern[j + 1] == pattern[i]:
            j += 1
        table.append(j + 1)
    return table

def kmp_search(text, pattern):
    table = build_prefix_table(pattern)
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
        elif j != 0:
            j = table[j - 1]
        else:
            i += 1
    return j == len(pattern)

text = "hello world"
pattern = "world"
if kmp_search(text, pattern):
    position = text.index(pattern)
else:
    position = -1