刷题笔记合集🔗

关联子串

问题描述

给定两个字符串 和 ，如果字符串 中的字符，经过排列组合后的字符串中，只要有一个字符串是 的子串，则认为 是 的关联子串。

若 是 的关联子串，请返回子串在 的起始位置；

若不是关联子串，则返回 。

输入格式

输入两个字符串，分别为题目中描述的 和 。

输出格式

若 是 的关联子串，请返回子串在 的起始位置；

若不是关联子串，则返回 。

若 中有多个 的组合子串，请返回最小的起始位置。

样例输入

abc efghicbaiii

abc efghiccaiii

样例输出

5

-1

数据范围

• 输入的字符串只包含小写字母
• 两个字符串的长度范围 之间

题解

这道题乍看之下似乎要求解所有 的排列组合，然后在 中查找，但由于字符串长度可能高达 10 万，枚举所有排列显然会超时。

实际上，这题是一个经典的滑动窗口（或称"尺取法"）问题。核心思想是：不需要关心字符的具体排列顺序，只需要关心字符出现的频率。如果 的某个子串包含的字符与 完全相同（考虑字符频率），那么这个子串一定是 某个排列。

算法步骤如下：

1. 统计 中各字符的频率
2. 使用固定大小为 的滑动窗口在 上移动
3. 对于每个窗口，检查窗口内字符的频率分布是否与 相同
4. 如果找到匹配的窗口，返回窗口的起始位置
5. 如果遍历完 仍未找到匹配，返回 -1

实现细节：

• 为了高效检查字符频率是否匹配，我们可以维护一个差异计数器 total
• 当滑动窗口移动时，只需更新窗口进出字符对应的计数和 total
• 当 total 为 0 时，表示当前窗口与 完全匹配

这种方法的时间复杂度为 O(n+m)，其中 n 和 m 分别是 和 的长度。空间复杂度为 O(1)，因为字符集有限，我们只需要固定大小的数组或哈希表存储频率。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取两个字符串
str1, str2 = input().split()

def find_anagram_substring():
    len1, len2 = len(str1), len(str2)
    
    # 特殊情况处理：如果str1长度大于str2，不可能是子串
    if len1 > len2:
        return -1
    
    # 统计str1中各字符的频率
    char_count = [0] * 26  # 只包含小写字母
    for ch in str1:
        char_count[ord(ch) - ord('a')] += 1
    
    # 目标字符总数
    total = len1
    
    # 初始化滑动窗口
    for i in range(len1):
        idx = ord(str2[i]) - ord('a')
        # 只有当计数器大于0时，才表示这个字符是str1中的字符
        if char_count[idx] > 0:
            total -= 1
        char_count[idx] -= 1
    
    # 如果total为0，说明找到了匹配
    if total == 0:
        return 0
    
    # 滑动窗口扫描剩余部分
    for i in range(len1, len2):
        # 移除窗口左边的字符
        left_idx = ord(str2[i - len1]) - ord('a')
        # 如果计数值>=0，说明是str1中的字符，需要增加total
        if char_count[left_idx] >= 0:
            total += 1
        char_count[left_idx] += 1
        
        # 添加窗口右边的字符
        right_idx = ord(str2[i]) - ord('a')
        # 如果计数值>0，说明是str1中的字符，需要减少total
        if char_count[right_idx] > 0:
            total -= 1
        char_count[right_idx] -= 1
        
        # 检查是否找到匹配
        if total == 0:
            return i - len1 + 1
    
    # 没有找到匹配
    return -1

print(find_anagram_substring())

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    string str1, str2;
    cin >