# 438.Find All Anagrams in a String

**438.Find ALL Anagrams in a String**

难度:Easy

> 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明： 字母异位词指字母相同，但排列不同的字符串。 不考虑答案输出的顺序。

```
示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
 示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
```

方法：

1. 最原始的比较法: Hash table按序比较，时间复杂度O(nm),提交超时。

```
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if(s==p) return res;
        if(s.length()<p.length()) return res;
        int len=p.size();
        unordered_map<char,int>b1;
        for(auto i:p)
            b1[i]++;
        for(int i=0;i<s.length()-len+1;i++)
        {
            unordered_map<char,int>a1;
            int flag=0;
            for(int j=i;j<i+len;j++)
            {
                a1[s[j]]++;
            }
            for(int j=i;j<i+len;j++)
            {
                if(a1[s[j]]!=b1[s[j]])
                {
                    flag=1;
                    break;
                }
            }
            if(!flag) 
                res.push_back(i);
        }

        return res;
    }

};
```

1. 优化： Hash table+ slide window. 时间复杂度O(n)

```
lass Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        vector<int>sv(26,0);
        vector<int>pv(26,0);
        int len=p.length();
        for(auto c: p)
            ++pv[c-'a'];
        for(int i=0;i<s.length();i++)
        {
            if(i>=len) --sv[s[i-len]-'a'];
            ++sv[s[i]-'a'];
            if(sv == pv) res.push_back(i-len+1);
        }
        return res;
    }

};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/438.find_all_anagrams_in_a_string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.