Licking Exercise - 63 Find all anagrams in a string

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.输出说明
Output a series of integers,is the starting index of the substring,按照由小到大的顺序输出,整数之间以空格分隔.

If the starting index set is empty,则输出“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);//记录sThe number of occurrences of each character in 
	vector<int>pCount(26);//记录pThe number of occurrences of each character in 

	for (int i = 0; i < p_len; i++)//Iterates over a string each timep长度
	{
    
		sCount[s[i] - 'a']++;
		pCount[p[i] - 'a']++;
	}
	//Because the title indicates that the string is composed of lowercase letters,Therefore, the comparison of characters can be converted into comparison of numbers
	if (sCount == pCount)//数组相等
		res.emplace_back(0);//The matching subscript is0

	//滑动窗口
	for (int i = 0; i < s_len - p_len; i++)//注意i的下标
	{
    
		sCount[s[i] - 'a']--;//Iterates over one character at a timech,需要把sCount中chThe number of corresponding subscript occurrences is decremented by one
		sCount[s[i+p_len]-'a']++;//When the window slides to the next character,Increments the number of occurrences of the character by one

		if (sCount == pCount)//A judgment is made every time the window is slid
		{
    
			res.emplace_back(i+1);//Because here is the new one obtained after the window is moved one square to the rightsCount和pCount,So if the conditions are met,resis inserted at 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;
}