Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:s: "cbaebabacd" p: "abc"Output:[0, 6]Explanation:The substring with start index = 0 is "cba", which is an anagram of "abc".The substring with start index = 6 is "bac", which is an anagram of "abc". 

Example 2:

Input:s: "abab" p: "ab"Output:[0, 1, 2]Explanation:The substring with start index = 0 is "ab", which is an anagram of "ab".The substring with start index = 1 is "ba", which is an anagram of "ab".The substring with start index = 2 is "ab", which is an anagram of "ab".

---

• 字符串题。弄清楚Sliding Window algorithm之后简单。
• 首先对string p做hash。假设在string s上有一个window，如果匹配一个hash[i]，就对-- hash[i]的话，最终结果就是要找到一个window宽度为p.size()，同时所有hash[i]都为0，即所有字符都匹配。
• 基于这个思想，我们可以观察到
  • the sum of all hash[i] is always >=0;
  • count is the sum of all positive hash[i];
  • therefore, every hash[i] is zero if and only if count is 0.
• 有了这个原则后，我们可以用两个指针指向window的left和right，count初始为p.size()，实际上是sum(hash[i])。然后开始移动right来扩展window，如果匹配，则-- count，然后继续移动right去扩展window。同时-- hash[right]，即对当前window中的char的hash值进行修改。
• 如果window的宽度为p.size()，即right - left == p.size()，那么判断如果count == 0则代表所有hash[i]已经匹配了，也就是找到匹配的anagram了。然后把window向右移动，即++ left。同时如果原先s[left]是存在于p中的，即hash[left] >= 0，则++ count复原。同时原先left处的字符已经不在当前window里了，则++ hash[left]来复原。
• 算法里注意对right指针对应的char的操作都是--，对left指针的则是++。对right指针进行的修改，在left移出window时会都复原，这样可以保证每个window初始时值都是一样。
• Find All Anagrams in a String - LeetCode

1 // 2 //  main.cpp 3 //  LeetCode 4 // 5 //  Created by Hao on 2017/3/16. 6 //  Copyright © 2017年 Hao. All rights reserved. 7 // 8  9 #include 
        
         10 #include 
         
          11 #include 
          
           12 using namespace std;13 14 class Solution {15 public:16     vector
           
             findAnagrams(string s, string p) {17         vector
            
              vResult;18         19         // corner case20         if (s.empty() || p.empty() || s.size() < p.size()) return vResult;21         22         unordered_map
             
               hash;23 24 // hash chars in p25 for (auto ch : p)26 ++ hash[ch];27 28 // two points indicating the begin/end of the window29 // count actually means the sum of all positive hash[i], and the sum of all hash[i] is always >= 030 int left = 0, right = 0, count = p.size();31 32 while (right < s.size()) {33 // move window's right point rightward, if the char exists in p, decrease the count34 if (hash[s.at(right)] > 0)35 -- count;36 37 -- hash[s.at(right)];38 39 ++ right;40 41 // if the window's width == p.size(), then we have to slide window rightward for a new window, move the left point rightward42 if (right - left == p.size()) {43 // count == 0 if and only if every hash[i] == 0, means we find the anagram44 if (0 == count)45 vResult.push_back(left);46 47 // Only increase the count if the char exists in p48 if (hash[s.at(left)] >= 0)49 ++ count;50 51 ++ hash[s.at(left)];52 53 ++ left;54 }55 }56 57 return vResult;58 }59 };60 61 int main(int argc, char* argv[])62 {63 Solution testSolution;64 65 vector
              
                iVec = { "cbaebabacd", "abc", "abab", "ab"};66 vector
               
                 result;67 68 /*69 0 670 0 1 271 */72 for (int i = 0; i < iVec.size() - 1; i += 2) {73 result = testSolution.findAnagrams(iVec[i], iVec[i + 1]);74 75 for (auto it : result)76 cout << it << " ";77 cout << endl;78 }79 80 return 0;81 }