学步园

在一个大串中查找和另外一个字符串是anagram的子串。

比如，GetAnagram("abcdbcsdaqdbahs'', "scdcb'') ==> "cdbcs''。

思路：

用统计字符的方法来做。当然也可以用质数方法来做。

#include <iostream>
#include <vector>
#include <string>
#include <assert.h>
using namespace std;

int GetAna(const string& s, const string& sub)
{
	assert(!s.empty() && !sub.empty());
	vector<int> cnt(26);
	vector<int> tvec(26);
	int sum = sub.size();
	for (int i = 0; i < sum; ++i)
		++cnt[sub[i] - 'a'];
	int i = 0;
	int size = s.size();
	bool flag;
	while (i <= size-sum)
	{
		flag = true;
		//首先可以先检查当前子串有没有没出现过的字符
		//如果有，直接从未出现字符的下一个位置重新扫描
		for (int k = i+sum-1; k >= i; --k)
		{
			if (cnt[s[k]-'a'] == 0)
			{
				i = k + 1;
				flag = false;
				break;
			}
		}
		//如果当前子串的字符均出现过，开始扫描
		if (flag)
		{
			tvec = cnt;	//恢复初始的状态
			int j = i;
			for (; j < i+sum; ++j)
			{
				//找到出现的字符，就将该字符次
				if (tvec[s[j]-'a'] > 0)
					--tvec[s[j]-'a'];
				//字符出现字符次数已经为0，说明不匹配
				else
				{
					++i;
					break;
				}
			}
			//如果扫描完sum个字符正常退出循环，说明找到串，返回子串的开始下标
			if (j == i + sum)
				return (j-sum);
		}
	}
	return -1;
}

void main()
{
	string s("abcdbcsdaqdbahs");
	string sub("adcsq");
	cout << GetAna(s, sub) << endl;
}