1791.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 54 行

/*  This Code is Submitted by wywcgs for Problem 1791 on 2006-09-11 at 14:32:08 */ 
#include <cstdio>
#include <cctype>
#include <set>
#include <algorithm>
using namespace std;

const int N = 7;
const int L = 102400;

class Data {
public:
	int n[N];
	Data() { memset(n, 0, sizeof(n)); }
	void add(int, int);
	bool operator <(const Data&) const;
};
bool Data::operator <(const Data& d) const {
	for(int i = 0; i < N; i++)
		if(n[i] != d.n[i]) return n[i] < d.n[i];
	return false;
}
void Data::add(int m, int k) {
	int cnt = (n[m>>2]>>((m&3)<<3))&63;
	n[m>>2] &= ~(255<<((m&3)<<3));
	cnt += k;
	n[m>>2] |= cnt<<((m&3)<<3);
}

int main()
{
	set<Data> s;
	char word[L];
	int k, i, str[L];

	while(scanf("%d", &k) != EOF && k != 0) {
		Data d; getchar();
		gets(word); s.clear();
		int b = 0, e = 0;
		for(i = 0; word[i] != 0; i++) {
			if(!isalpha(word[i])) continue;
			str[e++] = isupper(word[i]) ? word[i]-'A' : word[i]-'a';
			d.add(str[e-1], 1);
			if(e < k) continue;
			else if(s.count(d)) break;
			s.insert(d);
			d.add(str[b++], -1);
		}
		printf("%d\n", i);
	}
	
	return 0;
}