字符匹配:查找包含字符集的子串-和谐系统
时间:2019-09-03 09:39:11
手机看文章
扫描二维码
随时随地手机看文章
[导读]实现一个挺高级的字符匹配算法:
给一串很长字符串,要求找到符合要求的字符串,例如目的串:123,1******3*****2,12******3这些都要找出来
其实就是一些和谐系统。。
与此题类似:给
实现一个挺高级的字符匹配算法:
给一串很长字符串,要求找到符合要求的字符串,例如目的串: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),
这样就找到一个符合条件的字串了,继续下去,可以求出所有符合条件的串,同时可以求出满足条件最短子串
*/
#include
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[255]={0};
int cnt[255]={0};
int cnt2[255]={0};
for(int i=0; i