力扣练习——70 串联所有单词的子串

string s,str;

vector words;

int n;

cin>>s;

cin>>n;

for(int i=0; i>str;

    words.push_back(str);

}

vector res=Solution().findSubstring(s, words);

if (res.size()> 0)

    for(int i=0; i 0)

            cout<<" ";

        cout<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43

}
2.输入说明
首先收入字符串s，

然后输入words中单词的数目n，

最后输入n个字符串，表示words中的单词
3.输出说明
按照索引由小到大顺序输出，或者输出-1.
4.范例
输入
barfoothefoobarman
2
foo bar
输出
0 9
5.代码

#include
#include
#include
#include
#include
#include
#include
#include 

using namespace std;

vector<int> findSubstring(string s, vector<string> words)
{
	int word_len = words[0].size();//每个单词长度
	int s_len = s.size();
	int word_cnt = words.size();//总共有m个单词
	if (word_len == 0 || s_len == 0 || word_cnt == 0) return vector<int>{};

	unordered_map<string, int>word;//记录每个单词出现的次数
	for (auto it : words)
		word[it]++;

	vector<int> res;//结果
	
	unordered_map<string, int>tmp;
	
	int j;
	for (int i = 0; (i+ word_len*word_cnt ) <= s.size(); i++)//这里等号必须要加，否则会出错
	{
		for ( j = i; j < (i+word_len*word_cnt); j+=word_len)
		{
			string tmp_s = s.substr(j, word_len);//易错点1：substr(index,len) 第一个参数为下标，第二个为截取的长度
			//判断截取的子串是否存在于word中，且次数是否相等
			if (word[tmp_s] == 0)//不存在该单词，直接退出
				break;
			else
			{
				tmp[tmp_s]++;//哈希表更新
				if (word[tmp_s] < tmp[tmp_s])//重复次数过多，也要退出
					break;
			}
		}
		
		if (j == (i + word_len * word_cnt))//遍历到末尾了
			res.push_back(i);	
		tmp.clear();//每次遍历结束都要清空临时哈希表
	}
	return res;
}
int main()

{

	string s, str;

	vector<string> words;

	int n;

	cin >> s;

	cin >> n;

	for (int i = 0; i < n; i++)

	{

		cin >> str;

		words.push_back(str);

	}

	vector<int> res = findSubstring(s, words);

	if (res.size() > 0)

		for (int i = 0; i < res.size(); i++)

		{

			if (i > 0)

				cout << " ";

			cout << res[i];

		}

	else

		cout << -1;



	return 0;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99