找回密码
 用户注册

QQ登录

只需一步,快速开始

查看: 8244|回复: 0

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

[复制链接]
发表于 2012-5-23 21:33:38 | 显示全部楼层 |阅读模式
实现一个挺高级的字符匹配算法:
给一串很长字符串,要求找到符合要求的字符串,例如目的串: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),这样就找到一个符合条件的字串了,继续下去,可以求出所有符合条件的串,同时可以求出满足条件最短子串*/
  1. #include <iostream>
  2. using namespace std;
  3. void MinSubString( char *src, char *des )
  4. {
  5.         int min=1000;//找最短子串
  6.         int minfront=0;//最短子串开始位置
  7.         int minrear=0;//最短子串结束位置
  8.         int front,rear;
  9.         front=rear=0;
  10.         int len=strlen(des);
  11.         int hashtable[255]={0};
  12.         int cnt[255]={0};
  13.         int cnt2[255]={0};
  14.         for(int i=0; i<len; i++)//将字符集里的字符映射到hashtable数组中,方便判断src中的某个字符是否在字符集中
  15.                 hashtable[*(des+i)]=1;
  16.         int count=0;
  17.         char *p=src;
  18.         while( *(p+rear) !='\0')
  19.         {
  20.                 if(hashtable[*(p+rear)]==1)//rear当前字符在字符集中
  21.                 {
  22.                         if(cnt2[*(p+rear)]==0)//判断是否是本子串中第一次检索到此字符,由count统计字符集中已出现的字符数
  23.                         {
  24.                                 count++;
  25.                                 cnt[*(p+rear)]++;
  26.                                 cnt2[*(p+rear)]++;
  27.                                 if(count == len)//字符集中的字符在本子串中都已检索到
  28.                                 {
  29.                                         while(1)
  30.                                         {
  31.                                                 if(hashtable[*(p+front)]==1)//front当前字符在字符集中
  32.                                                 {
  33.                                                         cnt[*(p+front)]--;
  34.                                                         if(cnt[*(p+front)]==0)//字符集中某个字符为0,此时front到rear所指字符串即为符合条件的子串
  35.                                                         {
  36.                                                                 for(i=front; i<=rear; i++)//打印此子串
  37.                                                                         cout<<*(p+i);
  38.                                                                 cout<<endl;
  39.                                                             if(rear-front+1<min)
  40.                                                                 {
  41.                                                                         min=rear-front+1;
  42.                                                                         minrear=rear;
  43.                                                                         minfront=front;
  44.                                                                 }
  45.                                                                 //开始另一个串的检索时,要将count和cnt2[]清零。cnt[]不用变
  46.                                                                 count=0;
  47.                                                                 for(i=0; i<255; i++)
  48.                                                                         cnt2[i]=0;
  49.                                                                 front++;
  50.                                                                 break;                                                               
  51.                                                         }                                
  52.                                                 }
  53.                                                 front++;
  54.                                         }
  55.                                 }
  56.                         }
  57.                         else
  58.                         {
  59.                                 cnt[*(p+rear)]++;        
  60.                                 cnt2[*(p+rear)]++;        
  61.                         }
  62.                 }//当前字符不在字符集中
  63.                 rear++;
  64.         }
  65.         cout<<"最短子串:";
  66.         for(i=minfront ; i<=minrear; i++)
  67.                 cout<<*(p+i);
  68.         cout<<endl;
  69. }
  70. void main()
  71. {
  72.         char *src="ab1dkj2ksjf3ae32ks1iji2sk1ksl3ab;iksaj1223";
  73. //        char *src="2sk1ksl3ab;iksaj1223";
  74.         char *des="123";
  75.         MinSubString( src, des );
  76. }
复制代码


您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

Archiver|手机版|小黑屋|ACE Developer ( 京ICP备06055248号 )

GMT+8, 2024-3-29 10:16 , Processed in 0.013574 second(s), 7 queries , Redis On.

Powered by Discuz! X3.5

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表