#3813. 练4-魔法异位探寻

练4-魔法异位探寻

🏫 兔猫信奥学院:魔法异位探寻

在兔猫信奥学院的神秘图书馆中,小兔和小猫正在研究加菲老师遗留下来的魔法古卷。古卷中隐藏着一段神秘咒语,记载为一个字符串 ss。加菲老师曾告诫他们:“只要能在咒语中找到所有与另一段关键咒语 pp 互为异位词的片段,就能开启通往宝藏的秘密之门!”

异位词,指两个字符串中字符出现次数完全相同,但排列顺序可能不同。例如,"abc""abc""cba""cba" 就互为异位词。

小兔和小猫决定按照加菲老师的指示,仔细分析古卷,找出所有满足条件的子串的起始索引。现在,就请你帮忙解决这个谜题吧!


💡【题目描述】

给定两个字符串 sspp,请你找出字符串 ss 中所有 pp异位词的子串,并返回这些子串的起始索引。不考虑答案输出的顺序。

提示:

  • 子串是指字符串中的连续一段字符。
  • 两个字符串互为异位词,当且仅当它们包含的字符及出现的次数完全相同。

📥【输入格式】

  • 第一行包含两个整数 nnmm,分别表示字符串 sspp 的长度。
  • 第二行给出字符串 ss,仅包含小写字母。
  • 第三行给出字符串 pp,仅包含小写字母。

📤【输出格式】

  • 输出一个整数数组,表示所有满足条件的子串在 ss 中的起始索引(从 00 开始计数),各索引间以空格分隔。

📌【数据范围】

  • 1n,m3×1041 \leq n, m \leq 3 \times 10^4
  • sspp 均仅包含小写字母。

💡【输入输出样例】

样例输入 1

10 3
cbaebabacd
abc

样例输出 1

0 6

解释:起始索引为 00 的子串 "cba""cba""abc""abc" 互为异位词,索引 66 处的子串 "bac""bac" 亦然。


样例输入 2

4 2
abab
ab

样例输出 2

0 1 2

解释:子串 "ab""ab"(索引 0022)以及 "ba""ba"(索引 11)均为 "ab""ab" 的异位词。