[LintCode] Substring Anagrams

不是专门刷LintCode也没时间没耐心，只是刷贴吧看到这个问题就看了一下发现Python真的太棒了。

Substring Anagrams.png

网上有符合要求的代码，反正也只是简单难度。
我自己随便思考出来的方法似乎会超时，见求教各位，这题怎么搞？一贴。
总之就是由于无序而转为统计每个字符出现的个数并比较。
这个思路的C++11版代码，没测试是否超时

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;


void func(string word, map<char, size_t>& count)
{
    for (size_t i = 0; i <= word.size(); ++i)
    {
        auto ret = count.insert({ word[i],1 });
        if (!ret.second)
            ++ret.first->second;
    }
}

int main() {
    //string s = "cbaebabacd";
    //string p = "abc";
    string s = "abab";
    string p = "ab";
    vector<int> vec;
    map<char, size_t> word_count2;
    func(p, word_count2);
    for (size_t i = 0; i<s.size() - p.size() + 1; ++i)
    {
        map<char, size_t> word_count1;
        func(s.substr(i, p.size()), word_count1);
        if (word_count1 == word_count2)
            cout << i;
            vec.push_back(i);
    }
    return 0;
}

这个思路的Python版代码，虽然测试确定会超时，毕竟Python性能差，胜在简洁

from collections import Counter
def func(s, p):
    return [i for i in range(len(s)-len(p)+1) if Counter(s[i:i+len(p)]) == Counter(p)]

s, p = "cbaebabacd", 'abc'
print(func(s, p))

问题出在哪呢，真的只是算法本身选的不好吗？
灯光说是字符串切片成本太高，改成前后连接比较好。代码就不再写了。贴吧也有已经AC的代码。