[题解]ZOJ Monthly, December 2010 » ZOJ3455

ZOJ3455
ZOJ3455.cpp


#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXL = 500500;
const int SIGMA = 256;

int c[SIGMA];
int l[MAXL];
char str[MAXL];
char pat[MAXL];

int main() {
	int n, m, k;
	vector<int> ans;

	while (scanf("%s%s", str, pat) != EOF) {
		n = strlen(str);
		m = strlen(pat);
		fill(c, c + SIGMA, 0);
		for (int i = 0; i < m; ++i) {
			++c[pat[i]];
		}

		fill(l + 1, l + 1 + m, 0);
		for (int i = 0; i < SIGMA; ++i) {
			--l1];
		}
		k = count(l + 1, l + 1 + m, 0);

		ans.clear();
		fill(c, c + SIGMA, 0);
		for (int i = 0; i < n; ++i) {
			if (i >= m) {
		//		puts("DO");
				int& cc = c[str[i - m]];
				switch (l[cc]) {
				case 0: --k; break;
				case 1: ++k; break;
				}
				--l[cc];
				--cc;
				++l[cc];
				if (cc != 0) {
					switch (l[cc]) {
					case 0: ++k; break;
					case 1: --k; break;
					}
				}
			}

			int& cc = c[str[i]];
		//	printf("%d %d [%d %d %d %d]\n", cc, k, l[1], l[2], l[3], l[4]);
			if (cc != 0) {
				switch (l[cc]) {
				case 0: --k; break;
				case 1: ++k; break;
				}
			}
			--l[cc];
			++cc;
			++l[cc];
			switch (l[cc]) {
			case 0: ++k; break;
			case 1: --k; break;
			}
		//	printf("%d %d [%d %d %d %d]\n\n", cc, k, l[1], l[2], l[3], l[4]);

			if (k == m) {
				ans.push_back(i - m + 1);
			}
		}

		if (ans.empty()) {
			puts("No");
		} else {
			puts("Yes");
			for (int i = 0; i < (int)ans.size(); ++i) {
				printf("%d%c", ans[i], i == (int)ans.size() - 1 ? '\n' : ' ');
			}
		}
	}

	return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//612 	2010-12-23 20:03:31 	Accepted 	K 	C++ 	300 	6192 	watashi@Zodiac 	Source
Leave a Reply