原题

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;
    }
};