字符匹配：查找包含字符集的子串-和谐系统
实现一个挺高级的字符匹配算法：给一串很长字符串，要求找到符合要求的字符串，例如目的串：123,1******3*****2,12******3这些都要找出来
其实就是一些和谐系统。。
与此题类似：给一个很长的字符串str， 还有一个字符集比如{a，b，c}，找出str包含{a，b，c}的最短子串，要求O（n）。
/*用两个变量 front,rear 指向一个的子串区间的头和尾（当然，开始时front和rear都指向字符串开始处）。用一个int cnt={0}记录当前这个子串里字符集a,b,c各自的个数，一个变量count记录字符集里有多少个了rear 一直加，更新cnt[]和count的值，直到count等于字符集个数然后front++,直到cnt[]里某个字符个数为0（front 开始的部分有可能和后面的重复，所以front要加到某个字符个数为0），这样就找到一个符合条件的字串了,继续下去，可以求出所有符合条件的串，同时可以求出满足条件最短子串*/
#include <iostream>
using namespace std;
void MinSubString( char *src, char *des )
{
int min=1000;//找最短子串
int minfront=0;//最短子串开始位置
int minrear=0;//最短子串结束位置
int front,rear;
front=rear=0;
int len=strlen(des);
int hashtable={0};
int cnt={0};
int cnt2={0};
for(int i=0; i<len; i++)//将字符集里的字符映射到hashtable数组中，方便判断src中的某个字符是否在字符集中
hashtable[*(des+i)]=1;
int count=0;
char *p=src;
while( *(p+rear) !='\0')
{
if(hashtable[*(p+rear)]==1)//rear当前字符在字符集中
{
if(cnt2[*(p+rear)]==0)//判断是否是本子串中第一次检索到此字符，由count统计字符集中已出现的字符数
{
count++;
cnt[*(p+rear)]++;
cnt2[*(p+rear)]++;
if(count == len)//字符集中的字符在本子串中都已检索到
{
while(1)
{
if(hashtable[*(p+front)]==1)//front当前字符在字符集中
{
cnt[*(p+front)]--;
if(cnt[*(p+front)]==0)//字符集中某个字符为0，此时front到rear所指字符串即为符合条件的子串
{
for(i=front; i<=rear; i++)//打印此子串
cout<<*(p+i);
cout<<endl;
if(rear-front+1<min)
{
min=rear-front+1;
minrear=rear;
minfront=front;
}
//开始另一个串的检索时，要将count和cnt2[]清零。cnt[]不用变
count=0;
for(i=0; i<255; i++)
cnt2=0;
front++;
break;
}
}
front++;
}
}
}
else
{
cnt[*(p+rear)]++;
cnt2[*(p+rear)]++;
}
}//当前字符不在字符集中
rear++;
}
cout<<"最短子串：";
for(i=minfront ; i<=minrear; i++)
cout<<*(p+i);
cout<<endl;
}
void main()
{
char *src="ab1dkj2ksjf3ae32ks1iji2sk1ksl3ab;iksaj1223";
// char *src="2sk1ksl3ab;iksaj1223";
char *des="123";
MinSubString( src, des );
}
页:
[1]