字符匹配：查找包含字符集的子串-和谐系统

winston

实现一个挺高级的字符匹配算法：
给一串很长字符串，要求找到符合要求的字符串，例如目的串：123,1******3*****2,12******3这些都要找出来
其实就是一些和谐系统。。
与此题类似：给一个很长的字符串str， 还有一个字符集比如{a，b，c}，找出str包含{a，b，c}的最短子串，要求O（n）。
/*用两个变量 front,rear 指向一个的子串区间的头和尾（当然，开始时front和rear都指向字符串开始处）。用一个int cnt[255]={0}记录当前这个子串里字符集a,b,c各自的个数，一个变量count记录字符集里有多少个了rear 一直加，更新cnt[]和count的值，直到count等于字符集个数然后front++,直到cnt[]里某个字符个数为0（front 开始的部分有可能和后面的重复，所以front要加到某个字符个数为0），这样就找到一个符合条件的字串了,继续下去，可以求出所有符合条件的串，同时可以求出满足条件最短子串*/

2. #include <iostream>
3. using namespace std;
5. void MinSubString( char *src, char *des )
6. {
7.         int min=1000;//找最短子串
8.         int minfront=0;//最短子串开始位置
9.         int minrear=0;//最短子串结束位置
10.         int front,rear;
11.         front=rear=0;
12.         int len=strlen(des);
13.         int hashtable[255]={0};
14.         int cnt[255]={0};
15.         int cnt2[255]={0};
16.         for(int i=0; i<len; i++)//将字符集里的字符映射到hashtable数组中，方便判断src中的某个字符是否在字符集中
17.                 hashtable[*(des+i)]=1;
18.         int count=0;
19.         char *p=src;
20.         while( *(p+rear) !='\0')
21.         {
22.                 if(hashtable[*(p+rear)]==1)//rear当前字符在字符集中
23.                 {
24.                         if(cnt2[*(p+rear)]==0)//判断是否是本子串中第一次检索到此字符，由count统计字符集中已出现的字符数
25.                         {
26.                                 count++;
27.                                 cnt[*(p+rear)]++;
28.                                 cnt2[*(p+rear)]++;
29.                                 if(count == len)//字符集中的字符在本子串中都已检索到
30.                                 {
31.                                         while(1)
32.                                         {
33.                                                 if(hashtable[*(p+front)]==1)//front当前字符在字符集中
34.                                                 {
35.                                                         cnt[*(p+front)]--;
36.                                                         if(cnt[*(p+front)]==0)//字符集中某个字符为0，此时front到rear所指字符串即为符合条件的子串
37.                                                         {
38.                                                                 for(i=front; i<=rear; i++)//打印此子串
39.                                                                         cout<<*(p+i);
40.                                                                 cout<<endl;
41.                                                             if(rear-front+1<min)
42.                                                                 {
43.                                                                         min=rear-front+1;
44.                                                                         minrear=rear;
45.                                                                         minfront=front;
46.                                                                 }
47.                                                                 //开始另一个串的检索时，要将count和cnt2[]清零。cnt[]不用变
48.                                                                 count=0;
49.                                                                 for(i=0; i<255; i++)
50.                                                                         cnt2[i]=0;
51.                                                                 front++;
52.                                                                 break;                                                               
53.                                                         }                                
54.                                                 }
55.                                                 front++;
56.                                         }
57.                                 }
58.                         }
59.                         else
60.                         {
61.                                 cnt[*(p+rear)]++;        
62.                                 cnt2[*(p+rear)]++;        
63.                         }
64.                 }//当前字符不在字符集中
65.                 rear++;
66.         }
69.         cout<<"最短子串：";
70.         for(i=minfront ; i<=minrear; i++)
71.                 cout<<*(p+i);
72.         cout<<endl;
78. }
80. void main()
81. {
82.         char *src="ab1dkj2ksjf3ae32ks1iji2sk1ksl3ab;iksaj1223";
83. //        char *src="2sk1ksl3ab;iksaj1223";
84.         char *des="123";
85.         MinSubString( src, des );
88. }

复制代码