学步园

一，题目

        给一串很长字符串，要求找到符合要求的字符串，例如目的串：123
        例如：1******3***2 ,12*****3这些都要找出来
                  生活中，比如输入：法你轮和功    会被和谐的

二，分析：
       自然匹配就是对待匹配的每个字符挨个匹配，设你的待匹配字串长度位n,模式字符串长度位m。对于待匹配字符串中的任意一个字符最坏情况下要匹配m次，也就是说这个字符不在模式字符串中。所以最坏情况下总共是m*n此匹配，时间复杂度就是O(m*n)

       倘若使用hash表对待字符串进行hash处理O(n)的时间复杂度，那么对于模式字符串中的任意字符，仅需一次hash判断就可以得知是否在待匹配字符串中出现。最坏仅需m次就可以得到结果。时间复杂度为O(m)或者O(n);

       与此题相类似：就是给一个很长的字符串str还有一个字符集比如{a,b,c}找出str里包含{a,b,c}的最短子串。要求O(n)?比如，字符集是a,b,c，字符串是abdcaabcx，则最短子串为abc。

       用两个变量front rear指向一个的子串区间的头和尾，用一个int  
cnt[255]={0}记录当前这个子串里字符集a,b,c各自的个数，一个变量sum记录字符集里有多少个了rear一直加，更新cnt[]和sum的值，直到
sum等于字符集个数然后front++,直到cnt[]里某个字符个数为0，这样就找到一个符合条件的字串了继续前面的操作，就可以找到最短的了。

        鉴于此题的解答，我给出的答案是，利用哈希表（散列表）即根据关键码值(Key value)而直接进行访问的数据结构。下面源码是给出的基于ASCII码表的和谐过程。如果是汉字的，将会更复杂些。这里没有给出。不过，思路类似。

三，源码

#include <iostream>
using namespace std;
 
//强大的和谐系统
int main()
{
	char *src="anbmcj"; 
	char *des="abc";
	
	//创建一个哈希表，并初始化
	const int tableSize = 256; //因为ASCII码共有256个 
	int hashTable[tableSize];
	int len,i;

	for(i = 0; i < tableSize; i++)
		hashTable[i] = 0;

	len = strlen(src);
	for(i = 0; i < len; i++)
		hashTable[src[i]] = 1;

	len = strlen(des);
	for(i = 0; i < len; i++)
	{
		if(hashTable[des[i]] == 0)//如果des中的任何一个字母没有，则匹配失败 
		{
			cout<<"和谐失败，为正规内容"<<endl;  
		}     
	}
	
	 cout<<"您的内容被和谐"<<endl; 
	
	return 1;    //匹配成功
}

附表：