用 Python 编写的程序，用于查找 T 中字符串 S 的所有字谜的起始索引

pythonserver side programmingprogramming更新于 2026/2/15 6:04:17

假设我们有两个字符串 S 和 T，我们必须在 T 中找到 S 的所有字谜的起始索引。字符串仅由小写字母组成，并且字符串 S 和 T 的长度不会大于 20 和 100。

因此，如果输入为 S = "cab" T = "bcabxabc"，则输出将为 [0, 1, 5, ]，因为子字符串 "bca"、"cab"和"abc"。

为了解决这个问题，我们将遵循以下步骤:

定义一个映射 m，n := s 的大小，设置 left := 0，right := 0，counter := p 的大小
定义一个数组 ans
将 p 中字符的频率存储到映射 m 中
对于 right := 0 到 n – 1
- 如果 m 有 s[right] 且 m[s[right]] 非零，则将 m[s[right]] 减少 1，将 counter 减少 1，如果 counter = 0，则将 left 插入 ans
- 否则
  - 当 left < right，
    - 如果 s[left] 不存在于 m 中，则计数器增加 1，并将 m[s[left]] 增加 1
    - 将 left 增加 1
    - 如果 m 具有 s[right] 且 m[s[right]] 非零，则将 right 减少 1，并退出循环
  - 如果 m 没有 s[left]，则设置 left := right + 1
返回 ans

让我们看看以下实现以便更好地理解:

示例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> findAnagrams(string s, string p) {
      map <char, int> m;
      int n = s.size();
      int left = 0, right = 0;
      int counter = p.size();
      vector <int> ans;
      for(int i = 0; i < p.size(); i++) m[p[i]]++;
      for(int right = 0; right < n; right++){
         if(m.find(s[right]) != m.end() && m[s[right]]){
            m[s[right]]--;
            counter--;
            if(counter == 0)ans.push_back(left);
         } else {
            while(left<right){
               if(m.find(s[left]) != m.end()) {
                  counter++;
                  m[s[left]]++;
               }
               left++;
               if(m.find(s[right]) != m.end() && m[s[right]]){
                  right--;
                  break;
               }
            }
            if(m.find(s[left])==m.end())left = right + 1;
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.findAnagrams("bcabxabc", "cab")) ;
}