substring-with-concatenation-of-all-words

题目描述

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

题解

为什么强调长度相同呢？想到的两种比较暴力的方法：一种是找到s中各个单词的位置，组合起来选出符合要求的；一种是列出单词的全部组合，与s进行匹配。学习了别人的比较好的想法：

假设words数组长度为L，word单词长度为WL,遍历字符串s, 下标记做i，需要比对的单词起始坐标则为 [i, i+WL, i+2WL … i+(L-1)WL]如果i满足条件，各个单词的第k位之和一定相等
即：words[0][k] + words[1][k] + … + words[L-1][k] == s[i + k] + s[i+WL + k] + … + s[i+(L-1)WL + k]
反之，若对于i，满足后者条件的i则可能为正确结果，这个时候直接校验即可。

总结：先找出符合特征的下标，再对符合下标的结果进行校验，完全符合则输出。
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/jian-dan-you-xiao-lu-de-jie-fa-by-luqihang/

上面可能都是废话。还是好好学学别人的吧

先把存在的字符串，放到 hashmap ，可以快速比较，然后每一个位置都进行匹配
但这里会有很多的重复计算，就可以使用一个小技巧，先计算目标串的每个字母的 ASCII 和，
然后和当前要匹配的字符串的每个字母的 ASCII 进行比较，如果不相等就不用进行下面的匹配过程了
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/bao-li-suan-fa-jia-ru-qu-zhong-you-hua-10bei-ti-su/

vector<int> findSubstring1(string s, vector<string>& words) {
	vector<int> res;
	if (words.size()<1 || s.size()<1 || s.size() < words[0].size()*words.size()) return res;
	int wordLen = words[0].size(), lens = wordLen * words.size(), target = 0, cur = 0;
	unordered_map<string, int> allWord;
	for (auto& it : words) {
		allWord[it]++;
		for (auto& i : it) target += i;
	}
	for (int i = 0; i<lens; i++) cur += s[i];
	// 先看当前字符串的 ASCII 码相加是否相等 方便去重
	for (int i = 0, j; i <= s.size() - lens; cur -= s[i], cur += s[lens + i++]) {
		// 快速去重
		if (cur != target) continue;
		// 确认一下，是否为真的匹配
		unordered_map<string, int> tem(allWord);
		for (j = i; j<i + lens; j += wordLen)
			if (tem[s.substr(j, wordLen)]-- == 0) break;
		if (j == i + lens) res.push_back(i);
	}
	return res;
}

我是真的菜。不过新年快乐！

s.substr(0,5); //获得字符串s中从第0位开始的长度为5的字符