字符串相关例题（查询子串在主串中的个数）

子串出现的次数

题目描述

给定两个字符串 s1 和 s2 ，求 s2 在 s1 中出现的次数，字符区分大小写，已匹配的字符不计入下一次匹配

输入输出描述

输入两行字符串，分别为s1和s2，s2的长度小于等于s1

输出s2在s1中出现的次数

示例1

输入：

ABCsdABsadABCasdhjabcsaABCasd

ABC

输出：

3

示例2

输入：

AAAAAAAA

AAA

输出：

2

解题代码

1.遍历解法

def solve(s1,s2):
    if s1=="" and s2=="":
        return 1
    elif s1!="" and s2=="":
        return 0
    elif s1=="" and s2!="":
        return 0
    i=0
    count=0
    while i<len(s1):
        j=i
        k=0
        if s1[i]==s2[0]:
            j+=1
            k+=1
            while j<len(s1) and k<len(s2):
                if s1[j]==s2[k]:
                    j+=1
                    k+=1
            else:
                if k==len(s2):
                    count+=1
                    i=j
                if j==len(s1):
                    return count
        else:
            i+=1
    return count

s1=input()
s2=input()
print(solve(s1,s2))

2.滑动窗口结合字符串切片

def solve(s1,s2):
    #可以判断子串是否为空，根据题目
    if not s2:
        return "子串为空"
    #判断是否子串长于主串
    if len(s1)<len(s2):
        return "子串长于主串"
    i=0
    count=0
    while i<len(s1)-len(s2):
        if s1[i:i+len(s2)]==s2:
            count+=1
            i+=len(s2)
        else:
            i+=1
    return count

s1=input()
s2=input()
print(solve(s1,s2))

3.kmp算法

def count_substrings_kmp(s1, s2):
    # 特殊情况处理
    if not s2:
        return 0
    len1, len2 = len(s1), len(s2)
    if len2 > len1:
        return 0

    # 步骤1：构建LPS数组（最长公共前后缀数组）
    def build_lps(pattern):
        lps = [0] * len(pattern)
        length = 0  # 记录当前最长公共前后缀的长度
        i = 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    # 回溯到上一个可能的匹配位置
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps

    lps = build_lps(s2)
    count = 0
    i = 0  # i遍历s1
    j = 0  # j遍历s2

    while i < len1:
        if s1[i] == s2[j]:
            i += 1
            j += 1

        # 匹配成功一次
        if j == len2:
            count += 1
            j = 0  # 重置s2指针，寻找下一个非重叠匹配
            # 注意：此处i已自动跳过当前匹配的子串（因i在匹配时递增）

        # 匹配失败时的处理
        elif i < len1 and s1[i] != s2[j]:
            if j != 0:
                # 根据LPS数组回溯j，避免重复比较
                j = lps[j - 1]
            else:
                # j=0时直接移动i
                i += 1

    return count

# 读取输入
s1 = input().strip()
s2 = input().strip()

# 输出结果
print(count_substrings_kmp(s1, s2))