2014美团笔试之寻找最短子串

客官°小女子只卖身不卖艺 2022-01-06 15:39 250阅读 0赞

# **题目如图** #

![20141011115741093][]

# **实现代码** #

#include"iostream"
    #include"string"
    using namespace std;
    void Search(string &str,char p)
    {
    	for(string::iterator it=str.begin();it!=str.end();it++)
    		if(*it==p)
    		  {str.erase(it);
    	        return;}//单个字符只会出现一次,此时可以返回
    }
    void FindShortText(string text,string key)
    {
    	int Short=text.size()+1;
    	int Label=0;
    	for(int i=0;i<(text.size()-key.size());i++)
    	   {string temp(key);
    	    for(int j=0;j<=(text.size()-i-temp.size());j++)
    		{Search(temp,text[i+j]);
    		 if(temp.empty()&&(j+1)<Short)//当为空的时全部的字符已经匹配
    		    {Short=j+1;Label=i;break;}}
    	    if(Short==key.size())//若最短长度为key的长度，则没有必要继续，此为最好结果
    	        break;
    	    }
    	if(Short!=(text.size()+1))
              cout<<"从Text第"<<Label+1<<"个字符开始,满足条件的最小子字符串长度为"<<Short<<endl;
    	else
    	  cout<<"满足条件的子字符串不存在"<<endl;
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	string Text,Key;															
    	cout<<"分别输入Text和Key"<<endl;
            cin>>Text>>Key;
    	FindShortText(Text,Key);
    	return 0;
    }

# **程序分析** #

①使用完全遍历。遍历起点i，在i=[0 Text.size()-Key.size())遍历
       ②对于每个起点，对应相同的字符串temp=Key。
       ③从某个起点开始遍历后序字符，倘若字符在temp中出现，将该字符从temp中删除。
       ④倘若temp为空，即某个起点到当前位置j的子字符串已经能够匹配所有的字符。循环终止。将当前字符长度与最短子字符串长度Short比较，取最小值并记录位置。
       ⑤若最短子字符串长度为key的长度，没必要移动匹配起点，循环终止
       ⑥初始化Short最短长度为text.size()+1.若结果未变，代表没有找到存在的子串。

# **要点注意** #

①string迭代器的使用。见Search函数

②成员函数basic\_string::erasa

iterator erase(iterator first, iterator last)//删除[first last）范围内的元素,返回被删除的元素的前面的一个元素的迭代器类型or end() if no such element exists
     iterator erase(iterator it);//删除字符串中所有的 *it，返回被删除的元素的前面的一个元素的迭代器类型or end() if no such element exists
     basic_string& erase(size_type p0 = 0, size_type n = npos);//删除[0 n]的元素，并返回 当前string的引用.

③vector也有相同的使用。不过迭代器要声明类型：vector<int>::iterator it

④string的输入可以用空格和换行表示读入结束。可以直接用cin,cout输入输出

转载于:https://www.cnblogs.com/engineerLF/p/5393117.html

[20141011115741093]: /images/20211227/35d2efe0e5634ab48178b0292ec2319a.png