力扣练习——63 找到字符串中所有字母异位词

63 找到字符串中所有字母异位词

1.问题描述
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。

示例 1:

输入:

s: “cbaebabacd” p: “abc”

输出:

[0, 6]

解释:

起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。

起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。

示例 2:

输入:

s: “abab” p: “ab”

输出:

[0, 1, 2]

解释:

起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。

起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。

起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词。

2.输入说明
输入两个字符串s和p，只包含小写英文字母，长度都不超过 20100
3.输出说明
输出一系列整数，为子串的起始索引，按照由小到大的顺序输出，整数之间以空格分隔。

如果起始索引集合为空，则输出“none”，不包括引号。
4.范例
输入
cbaebabacd
abc
输出
0 6
5.代码

#include<iostream>
#include<map>
#include<string>
#include<unordered_map>
#include<algorithm>
#include<string.h>//memset函数
using namespace std;

vector<int> indexOfString(string s, string p)
{
    
	int s_len = s.size();//字符串s长度
	int p_len = p.size();//目标字符串长度
	if (s_len < p_len)
		return vector<int>();

	vector<int>res;
	vector<int>sCount(26);//记录s中每个字符出现次数
	vector<int>pCount(26);//记录p中每个字符出现次数

	for (int i = 0; i < p_len; i++)//每次都要遍历一个字符串p长度
	{
    
		sCount[s[i] - 'a']++;
		pCount[p[i] - 'a']++;
	}
	//因为题目表示字符串都是由小写字母组成，所以可以把字符的比较转化为数字的比较
	if (sCount == pCount)//数组相等
		res.emplace_back(0);//匹配的下标为0

	//滑动窗口
	for (int i = 0; i < s_len - p_len; i++)//注意i的下标
	{
    
		sCount[s[i] - 'a']--;//每次遍历完一个字符ch，需要把sCount中ch对应的下标出现数量减一
		sCount[s[i+p_len]-'a']++;//窗口滑动到下一个字符时，将字符出现的次数加一

		if (sCount == pCount)//每次滑动窗口时要进行判断
		{
    
			res.emplace_back(i+1);//因为这里是窗口向右移动一格后得到的新的sCount和pCount，所以若满足条件，res中插入的位置为i+1
		}
	}
	return res;
}


int main()

{
    
	string s, p;
	cin >> s >> p;
	vector<int>res = indexOfString(s, p);
	if (res.size() == 0)
		cout << "none" << endl;
	else
	{
    
    for (int i = 0; i < res.size()-1; i++)
	{
    
		cout << res[i] << " ";
	}
	cout << res[res.size() - 1] << endl;
	}
	
	return 0;
}