记录编号	1876	评测结果	AWAAAAAAAAAAAAAA
题目名称	翻译玛雅著作	最终得分	93
用户昵称	BYVoid	是否通过	未通过
代码语言	C++	运行时间	10.000 s
提交时间	2008-09-09 14:19:59	内存使用	0.00 MiB

#include <iostream>
#include <string>
#define MAX 30000001

using namespace std;

class queue
{
public:
	int q[MAX];
	int first,last,size;
	queue()
	{
		first=size=0;last=-1;
	}
	void ins(int k)
	{
		size++;
		q[++last]=k;
	}
	int pop()
	{
		size--;
		return q[first++];
	}
};

char S[MAX];
int G,L,ans;
int W['z'+1];
queue Q;


void init()
{
	int i;
	freopen("writing.in","r",stdin);
	freopen("writing.out","w",stdout);
	scanf("%d%d\n%s\n",&G,&L,&S);
	for (i=0;i<G;i++)
		W[ S[i] ]++;
	scanf("%s\n",&S);
}

bool check()
{
	int j;
	for (j='A';j<='Z';j++)
		if (W[j])
			return false;
	for (j='a';j<='z';j++)
		if (W[j])
			return false;
	return true;
}

void solve()
{
	int i,j,k;
	char c;
	for (i=0;i<L;i++)
	{
		if (check())
			ans++;
		c=S[i];
		if (W[c])
		{
			W[c]--;
			Q.ins(i);
		}
		else
		{
			while (Q.size)
			{
				k=Q.pop();
				if (S[k]==c)
				{
					Q.ins(i);
					break;
				}
				W[S[k]]++;
			}
		}
	}
}

int main()
{
	init();
	solve();
	cout << ans;
	return 0;
}