OpenJudge NOI 2.1 2472:子串计算

【题目链接】

OpenJudge NOI 2.1 2472:子串计算

【题目考点】

1. STL map

map原理是红黑树，可以存储一系列的键值对。以下给出map的一些基础用法：

• 声明对象：map<键类型, 值类型> map对象;
  map mp;
• 添加键值对：map对象[键] = 值;
  mp["1"] = 0
  如果该键不存在，则会新增一个键值对。
• 获取键出现的次数：map对象.count(键)
  例：mp.count("1") == 1
  如果该表达式为真，说明键"1"存在，否则不存在。
• 迭代器遍历map对象

map<string, int> mp;
//为mp添加一些键值对
for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++)
	cout << it->first << ' ' << it->second << endl;//it指向的数据类型是pair
1
2
3
4

2. 查找：顺序查找，二分查找

3. 排序

【解题思路】

解法1：使用STL map

设map类型对象mp，键为子串，值为子串的个数。这样使用mp对象，就能通过子串获取到子串的个数。
输入的字符串为s，枚举s的所有子串，方法为：

• 子串的起始位置i从第0位置循环到第s.length()-1位置
• 子串的长度最短为1，最长为取到末尾。末尾位置是s.length()-1，起始位置为i，最大长度为s.length()-1-i+1 = s.length()-i。
• 使用substr函数，根据子串起始位置和长度取出子串。

对于每个子串：

• 如果mp的键中存在该子串，那么该子串的个数（也就是该键对应的值），增加1。
• 如果mp的键中不存在该子串，那么就增加键值对，该子串的个数为1。

最后对mp进行迭代器遍历输出。对map类型对象使用迭代器遍历输出，得到的序列本身就是按键从小到大排列好的序列。
如果字符串s长度为n，那么子串个数数量级为$O(n^2)$，每次新建一个键值对，实际上是在红黑树中插入一个新的结点，复杂度为$O(log{n}^2)=O(logn)$，总体复杂度为$O(n^{2}logn)$

解法2：顺序查找+排序

设结点Node类型，包含字符串和其个数。设Node类型数组sub来记录已经找到的所有子串及其出现的个数。
字符串s的最大长度为100，子串个数为$1+2+...+100=5050$，将sub长度设为10005一定是够用的。
枚举输入的字符串s的所有子串，每看到一个子串，就通过顺序查找的方法看sub数组中是否已有有该子串：

• 如果有，其出现次数加1
• 如果没有，则添加由该子串构成的结点，子串出现次数为1。

枚举结束后，对sub数组根据每个元素的子串按字典序从小到大进行排序，而后遍历输出。
记输入字符串的长度为n，枚举子串的个数数量级为$O(n^2)$，每次顺序查找的复杂度也是$O(n^2)$，统计子串个数的过程就达到了$O(n^4)$，后面排序的复杂度为$O(n^{2}logn)$，整体复杂度为$O(n^4)$。

解法3：二分查找+插入排序

与解法2类似，设sub数组，保存Node类型对象，sub数组中的对象始终按子串字典序升序来排列。
每取到一个新的子串，通过二分查找看已有序列中是否存在该子串。

• 如果存在，则该子串数量加1。
• 如果不存在，则添加一个新才子串对象，数量为1。添加后，将新添加的子串对象通过插入排序的方法将新对象插入到按子串字典序从小到大排列的有序序列中。

该方法的复杂度为$O(n^{4}logn)$

【题解代码】

解法1：使用STL map

#include 
using namespace std;
map<string, int> mp;
int main()
{

	string s;
	cin >> s;
	for(int i = 0; i < s.length(); ++i)
	{
		for(int len = 1; len <= s.length()-i; ++len)//枚举可能的子串长度
		{
			string key = s.substr(i, len);
			if(mp.count(key) == 0)//其实把这个if...else替换为mp[key]++也能过，如果遇到不存在的键，会自动创建一个键值对。而key对应的值是从堆区申请的，int类型的值初值一定为0。
				mp[key] = 1;
			else
				mp[key]++; 
		} 	
	}
	for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		if(it->second > 1)
			cout << it->first << ' ' << it->second << endl;
	}
	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

解法2：顺序查找+排序

#include 
using namespace std;
#define N 10005
struct Node
{
	string s;//子串 
	int ct;//出现的个数 
};
Node sub[N];//sub[i]:第i个子串的信息
int sn; 
int findPos(string s)//顺序查找 返回sub中子串s的下标，如果不存在，返回0。 
{
	for(int i = 1; i <= sn; ++i)
		if(sub[i].s == s)
			return i;
	return 0;
}
bool cmp(Node a, Node b)//按照字符串字典序升序排序 
{
	return a.s < b.s;
}
int main()
{
	string s, str;
	cin >> s;
	for(int i = 0; i < s.length(); ++i)
	{
		for(int len = 1; len <= s.length()-i; ++len)
		{
			str = s.substr(i, len);
			int p = findPos(str);
			if(p == 0)
			{
				sub[++sn].s = str;
				sub[sn].ct = 1;
			}
			else
				sub[p].ct++;
		}
	}
	sort(sub+1, sub+1+sn, cmp);
	for(int i = 1; i <= sn; ++i)
	{
		if(sub[i].ct > 1)
			cout << sub[i].s << ' ' << sub[i].ct << endl;
	}
	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

解法3：二分查找+插入排序

#include 
using namespace std;
#define N 10005
struct Node
{
	string s;//子串 
	int ct;//出现的个数 
};
Node sub[N];//sub[i]:第i个子串的信息
int sn; 
int findPos(string s)//二分查找 如果sub中存在s，返回下标。不存在则返回0。 
{
	int l = 1, r = sn, mid;
	while(l <= r)
	{
		mid = (l+r)/2;
		if(sub[mid].s > s)
			r = mid - 1;
		else if(sub[mid].s < s)
			l = mid + 1;
		else
			return mid;
	}
	return 0;
}
int main()
{
	string s, str;
	cin >> s;
	for(int i = 0; i < s.length(); ++i)
	{
		for(int len = 1; len <= s.length()-i; ++len)
		{
			str = s.substr(i, len);
			int p = findPos(str);
			if(p == 0)//如果不存在 
			{
				sub[++sn].s = str;//新增元素 
				sub[sn].ct = 1;
				for(int j = sn; j > 1; --j)//将其插入到有序序列sub中 
				{
					if(sub[j].s < sub[j-1].s)
						swap(sub[j], sub[j-1]);
					else
						break;
				}
			}
			else//如果存在 
				sub[p].ct++;
		}
	}
	for(int i = 1; i <= sn; ++i)
	{
		if(sub[i].ct > 1)
			cout << sub[i].s << ' ' << sub[i].ct << endl;
	}
	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