LeetCode 29. Substring with Concatenation of All Words

暴力マッチング.
1枚のmapでLの単語と頻度を統計します;
もう1枚のmap再反復には、現在の反復の下にあるbeginから始まるサブ列の単語の周波数が記録され、現在の周波数が総周波数を超えると再反復します.

if (++ tmp[S.substr(begin+i*word_size, word_size)] > cnt[S.substr(begin+i*word_size, word_size)] )
{
<span style="white-space:pre">	</span>break;
}

完全なコード:

class Solution 
{
public:
	vector<int> findSubstring(string S, vector<string> &L) 
	{
		if( L.empty() == true )
		{
			return vector<int>();
		}
		vector<int> ret;
		map<string, int> cnt;
		int word_size = L[0].size();
		for (auto it = L.begin(); it != L.end(); ++ it)
		{
			++ cnt[*it];
		}    

		for (int begin = 0; begin <= int(S.size())-int(L.size()*word_size); ++ begin)
		{
			map<string, int> tmp;
			size_t i = 0;
			for ( ; i < L.size(); ++ i)
			{
				if (++ tmp[S.substr(begin+i*word_size, word_size)] > cnt[S.substr(begin+i*word_size, word_size)] )
				{
					break;
				}
			}
			if (i == L.size())
			{
				ret.push_back(begin);
			}
		}

		return ret;
	}
};