原题
LintCode 647. Substring Anagrams
Description
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 40,000.
The order of output does not matter.
Example
Given s = "cbaebabacd" p = "abc"
return [0, 6]
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".
解题
题意是给定一个字符串s和一个patternp，要求从s中找到p的任何一种排列出现的全部位置。
最最naive的解法就是首先对p进行全排列，然后在s中寻找每一种排列，不过这必然会超时。
合理的解法是：
假设s的长度为ssize，p长度为psize
对s进行窗口式的扫描，窗口的宽度为psize。也就是说每次都从s中取出psize个字符。
此时维护两个字母表，prr字母表用来记录p中所有字母出现的次数，srr字母表用来记录当前扫描的窗口中的所有字母的出现次数。
此时如果两个字母表相同，则表明窗口中的字符串和p的字母构成是一致的，也就是说窗口中的字符串是p的一个排列，那么只需要将窗口的起始位置加入答案即可。
优化
上述解法是，每次窗口移动的时候都统计一遍srr字母表，这做了很多无用功。
我们可以采用下述策略来维护字母表srr：
首次扫描的时候，完整统计窗口内所有字母的出现次数。
之后每次移动窗口的时候，将移出窗口的字母出现的次数 -1，将移入窗口的字母出现的次数 +1
代码
class Solution {
public:
/**
* @param s a string
* @param p a non-empty string
* @return a list of index
*/
vector<int> findAnagrams(string& s, string& p) {
// Write your code here
// 答案集合
vector<int> ans;
// 两个字母表
int srr[26] = { 0 }, prr[26] = { 0 };
int ssize = s.size(), psize = p.size();
if (ssize < psize) return ans;
// 首次扫描，完整统计窗口内字母出现的次数
for (int i = 0; i < psize; i++) srr[s[i] - 'a']++;
// 统计p中字母出现的次数
for (int i = 0; i < psize; i++) prr[p[i] - 'a']++;
for (int j = psize; j <= ssize; j++) {
bool isOK = true;
for (int i = 0; i < 26; i++) {
if (srr[i] != prr[i]) {
isOK = false;
break;
}
}
// 如果字母表完全相同，则将窗口初始位置加入答案
if (isOK) ans.push_back(j - psize);
if (j == ssize) return ans;
// 将移入窗口的字母出现次数 + 1
srr[s[j] - 'a']++;
// 将移出窗口的字母出现次数 - 1
srr[s[j - psize] - 'a']--;
}
return ans;
}
};
