E卷-刷题笔记合集🔗

关联子串

问题描述

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

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

输入格式

输入两个字符串，分别为 和 ，两个字符串之间用空格分隔。

输出格式

输出一个整数，表示关联子串在 中的起始位置（从 开始计数）。若 不是 的关联子串，则输出 。若 中有多个 的组合子串，请返回最小的起始位置。

样例输入1

abc efghicbaiii

样例输出1

5

样例输入2

abc efghiccaiii

样例输出2

-1

样例解释

样例1	包含 的一种排列组合（"cab"），此组合在 的起始位置为 5（从 0 开始计数）。
样例2	"abc" 字符串中三个字母的各种组合（abc、acb、bac、bca、cab、cba）， 中均不包含，因此返回 -1。

数据范围

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

题解

滑动窗口

这道题目乍看之下似乎需要生成 的所有排列组合，然后在 中查找。但是，考虑到字符串长度可能达到 100000，这种方法显然会导致时间复杂度过高。

实际上，这个问题可以通过滑动窗口（也称为尺取法）来高效解决。核心思想是：不需要真正生成 的所有排列，只需要确保 中某个子串包含了 中所有字符，且字符数量一致即可。

具体步骤如下：

1. 统计 中每个字符的出现次数，可以使用一个长度为 26 的数组 来记录（因为只有小写字母）。

2. 使用两个指针 和 在 上滑动，维护一个窗口。

3. 移动 指针扩大窗口，同时更新当前窗口中字符的计数。

4. 当窗口大小等于 的长度时，检查窗口中的字符是否恰好包含了 中的所有字符。

5. 如果匹配成功，返回 指针的位置。

6. 如果不匹配，移动 指针缩小窗口，继续步骤 3。

这种方法的时间复杂度是 ，其中 是 的长度。空间复杂度是 ，因为使用了固定大小的数组来计数。

参考代码

• Python

def find_anagram_substring(s1, s2):
    # 初始化计数数组，用于记录s1中每个字符的出现次数
    count = [0] * 26
    for c in s1:
        count[ord(c) - ord('a')] += 1
    
    # 初始化窗口
    window = [0] * 26
    left = right = 0
    
    while right < len(s2):
        # 扩大窗口
        window[ord(s2[right]) - ord('a')] += 1
        
        # 当窗口大小等于s1长度时，检查是否匹配
        if right - left + 1 == len(s1):
            if window == count:
                return left
            
            # 缩小窗口
            window[ord(s2[left]) - ord('a')] -= 1
            left += 1
        
        right += 1
    
    return -1

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

# 调用函数并输出结果
result = find_anagram_substring(s1, s2)
print(result)

• C

#include <stdio.h>
#include <string.h>

#define MAX_LEN 100001

int find_anagram_substring(char* s1, char* s2) {
    int count[26] = {0};
    int window[26] = {0};
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int left = 0, right = 0;

    // 统计s1中字符出现次数
    for (int i = 0; i < len1; i++) {
        count[s1[i] - 'a']++;
    }

    while (right < len2) {
        // 扩大窗口
        window[s2[right] - 'a']++;

        // 当窗口大小等于s1长度时，检查是否匹配
        if (right - left + 1 == len1) {
            int match = 1;
            for (int i = 0; i < 26; i++) {
                if (window[i] != count[i]) {
                    match = 0;
                    break;
                }
            }
            if (match) return left;

            // 缩小窗口
            window[s2[left] - 'a']--;
            left++;
        }

        right++;
    }

    return -1;
}

int m