算法11（给一个很长的字符串str 还有一个字符集比如{a,b,c} 找出str 里包含{a,b,c}的最短子串。要求O(n).)

http://blog.csdn.net/yuucyf/article/details/6714235

题目：

给一个很长的字符串str 还有一个字符集比如{a,b,c} 找出str 里包含{a,b,c}的最短子串。要求O(n).

比如，字符集是a,b,c，字符串是abdcaabcx，则最短子串为abc。

思路一：

用两个变量Front, Rear 指向这个字串(str)区间的头和尾，开始的时候同指向字符串首地址，用一个变量int achSubCnt[256]={0}记录字符集a,b,c 个数，用另外一个变量int achCnt[256] = {0}记录当前这个子串里a,b,c各自出现的个数，一个变量i32CurSum记录当前Front,Rear指向的区间中有多少个字符集里面的元素了，Rear 一直加，然后判断Rear所指的字符是否是在字符集中，如果是那么更新achCnt[]和i32CurSum的值，直到i32CurSum等于字符集个数，然后Front++，直到achCnt[]里某个字符个数为0，这样就找到一个符合条件的字串了。
继续前面的操作，就可以找到最短的了。（如果题目要求把所有匹配字符集中的字符串罗列出来也是可以的，这样还可以不进行匹配字串长度的比较）

代码如下：

[cpp] view plaincopyprint?

1. /*--------------------------------
2. Copyright by yuucyf. 2011.08.24
3. ---------------------------------*/
5. #include "stdafx.h"
6. #include <iostream>
7. using namespace std;
9. #define CHAR_COUNT 256
10. typedef struct tagPosition
11. {
12. int i32Front;
13. int i32Rear;
15. tagPosition()
16. {
17. i32Front = i32Rear = 0;
18. }
19. }S_StrPos;
22. bool FindShortSubString(const char* pszStr, const char *pszSubStr, S_StrPos &sShortSubStr)
23. {
24. if (NULL == pszStr || NULL == pszSubStr)
25. return false;
26. int i32Len = _tcslen(pszStr);
27. int i32SubLen = _tcslen(pszSubStr);
28. if (i32Len <= 0 || i32SubLen <= 0)
29. return false;
31. sShortSubStr.i32Front = sShortSubStr.i32Rear = 0;
33. int i32CurSum = 0;
34. int achSubCnt[CHAR_COUNT] = {0};
35. int achCnt[CHAR_COUNT] = {0};
36. int i32I = 0;
37. for (i32I = 0; i32I < i32SubLen; i32I++)
38. {
39. achSubCnt[pszSubStr[i32I]]++;
40. }
42. int Front = 0, Rear = 0;
43. while (Front < i32Len && Rear < i32Len)
44. {
45. if (i32CurSum != i32SubLen)
46. {
47. if (achSubCnt[pszStr[Rear]] > 0)
48. {
49. achCnt[pszStr[Rear]]++;
50. if (achSubCnt[pszStr[Rear]] >= achCnt[pszStr[Rear]])
51. i32CurSum++;
52. }
54. Rear++;
55. }
56. else
57. {
58. achCnt[pszStr[Front]]--;
59. if (achCnt[pszStr[Front]] == 0) //Find a sub string.
60. {
61. if (sShortSubStr.i32Rear == 0)
62. {
63. sShortSubStr.i32Front = Front;
64. sShortSubStr.i32Rear = Rear;
65. }
66. else if ((sShortSubStr.i32Rear - sShortSubStr.i32Front) > (Rear - Front))
67. {
68. sShortSubStr.i32Front = Front;
69. sShortSubStr.i32Rear = Rear;
70. }
72. i32CurSum--;
73. }
74. Front++;
75. }
76. }
78. //可能是Rear已经到达字符串尾，可是还存在i32CurSum == i32SubLen的情况，
79. //所以要从Front开始往前遍历，找到最后一个满足条件的字串。
80. while (i32CurSum == i32SubLen)
81. {
82. achCnt[pszStr[Front]]--;
83. if (achCnt[pszStr[Front]] == 0) //Find a sub string.
84. {
85. if (sShortSubStr.i32Rear == 0)
86. {
87. sShortSubStr.i32Front = Front;
88. sShortSubStr.i32Rear = Rear;
89. }
90. else if ((sShortSubStr.i32Rear - sShortSubStr.i32Front) > (Rear - Front))
91. {
92. sShortSubStr.i32Front = Front;
93. sShortSubStr.i32Rear = Rear;
94. }
96. i32CurSum--;
97. }
98. Front++;
99. }
101. return (sShortSubStr.i32Rear != 0);
102. }
105. int _tmain(int argc, _TCHAR* argv[])
106. {
107. char aszStr[] = "abdcaabcx";
108. char aszSubStr[] = "abc";
109. S_StrPos sStrPos;
111. if (FindShortSubString(aszStr, aszSubStr, sStrPos))
112. {
113. cout << "最短的字串为:";
114. for (int i32I = sStrPos.i32Front; i32I < sStrPos.i32Rear; i32I++)
115. cout << aszStr[i32I];
116. cout << endl;
117. }
118. return 0;
119. }