字符串匹配之通配符问题-
一串长为M的珠子,珠子的颜色有N种(N<10)。求包含N种颜色的最短连续珠串。
//两个指针,开始的时候都指向某一个位置,移动前一个指针,直到两个指针直接包含了所有颜色的珠子。
//此时记下len。
//然后向前移动后面的指针,再调整最前面的指针,直到重新满足两个指针间包含了所有的颜色,比较此时的len和之前的len,取最小值。
//如此移动,直到后面的指针回到起始位置。
//时间复杂度是O(N),空间复杂度是O(1)
#include<iostream>usingnamespacestd;voidSearch(char*src,char*ch){intvaries=0;//多少种颜色char*begin=src;memset(ch,0,sizeof(char)*256);while(*begin++){if(ch[*begin-'0']++==0){++varies;}}//此时varies存储共有多少种颜色intMinLength=0;intcurLength=0;char*prev=src;char*cur=src;intcurVaries=0;char*ret=NULL;memset(ch,0,sizeof(char)*256);while(1){curLength=0;curVaries=0;cur=prev;memset(ch,0,sizeof(char)*256);while(curVaries!=varies){if(++ch[*cur-'0']==1)curVaries++;++cur;++curLength;if(*cur=='\0')cur=src;}if(MinLength==0||MinLength>curLength){MinLength=curLength;ret=prev;}if(MinLength==varies)break;//得到最短的++prev;if(*prev=='\0')break;}intflag=1;intindex=0;for(inti=0;i<MinLength;++i){if(ret[i]=='\0')flag=0;if(flag==1)ch[i]=ret[i];elsech[i]=src[index++];}ch[MinLength]='\0';}voidTest1(){char*src="abbcdabcddddacgd";charch[256]={0};Search(src,ch);cout<<ch<<endl;}//所得结果应该是cgdab
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。