3805977_mle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <ctype.h>
#include <algorithm>
#define hsize 997001;
using namespace std;

int cnt[26];
char str[100001];
char sub[100001];
int c, k;
struct node
{
	int cnt[26];
	node(int v[26])
	{
		for (int i = 0; i < 26; i++)
			cnt[i] = v[i];
	}
	bool operator == (const node &t)	const
	{
		for (int i = 0; i < 26; i++)
			if (t.cnt[i] != cnt[i])
				return false;
		return true;
	}
};

vector <node> mark[1000001];
int flag = 0;

int insert()
{
	int i,p;
	for(p=0,i=0;i<26;i++)
		p=((p<<2)+(cnt[i]<<2))^(cnt[i]<<10);
	p=p%hsize;
	if(p<0)	p+=hsize;
	node t = node(cnt);
	for (i = 0; i < mark[p].size(); i++)
		if (mark[p][i] == t)
			return 0;
	mark[p].push_back(t);
	return 1;
}

int main()
{
	int i, len;

	//freopen("g.in", "r", stdin);
	//freopen("g.txt", "w", stdout);
	while (scanf("%d", &k) == 1)
	{
		getchar();
		if (k == 0)
		{
			break;
		}
		c = 0;
		flag++;
		gets(str);
		for (i = 0; i < 1000000; i++)
			mark[i].clear();
		memset(cnt, 0, sizeof(cnt));
		len = strlen(str);
		for (i = 0; str[i]; i++)
		{
			if (!isalpha(str[i]))
				continue;
			if (isupper(str[i]))
			{
				str[i] += ' ';
			}
			sub[c++] = str[i];
			cnt[str[i] - 'a']++;
			if (c >= k)
			{
				if (c > k)
					cnt[sub[c - k - 1] - 'a']--;
				if (!insert())
				{
					break;
				}
			}
		}
		if (c < k)
		{
			printf("%d\n", len);
			continue;
		}
		printf("%d\n", i);
	}
	return 0;
}