Parade Show

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 921 Accepted Submission(s): 386


Problem Description
2013 is the 60 anniversary of Nanjing University of Science and Technology, and today happens to be the anniversary date. On this happy festival, school authority hopes that the new students to be trained for the parade show. You should plan a better solution to arrange the students by choZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc2luZyBzb21lIHF1ZXVlcyBmcm9tIHRoZW0gcHJlcGFyaW5nIHRoZSBwYXJhZGUgc2hvdy4gKG9uZSBzdHVkZW50IG9ubHkgaW4gb25lIHF1ZXVlIG9yIG5vdCBiZSBjaG9zZW4pPGJyPgogIEV2ZXJ5IHN0dWRlbnQgaGFzIGl0cyBvd24gbnVtYmVyLCBmcm9tIDEgdG8gbi4gKDE8PW48PTEwXjUpLCBhbmQgdGhleSBhcmUgc3RhbmRpbmcgZnJvbSAxIHRvIG4gaW4gdGhlIGluY3JlYXNpbmcgb3JkZXIgdGhlIHNhbWUgd2l0aCB0aGVpciBudW1iZXIgb3JkZXIuIEFjY29yZGluZyB0byByZXF1aXJlbWVudCBvZiBzY2hvb2wgYXV0aG9yaXR5LCBldmVyeSBxdWV1ZSBpcyBjb25zaXN0ZWQgb2YgZXhhY3RseSBtIHN0dWRlbnRzLiBCZWNhdXNlCiBzdHVkZW50cyB3aG8gc3RhbmQgYWRqYWNlbnQgaW4gdHJhaW5pbmcgYXJlIGFzc2lnbmVkIGNvbnNlY3V0aXZlIG51bWJlciwgZm9yIGJldHRlciBhcnJhbmdlbWVudCwgeW91IHdpbGwgY2hvb3NlIGluIHN0dWRlbnRzIHdpdGggaW4gY29uc2VjdXRpdmUgbnVtYmVycy4gV2hlbiB5b3UgY2hvb3NlIHRoZXNlIG0gc3R1ZGVudHMsIHlvdSB3aWxsIHJlYXJyYW5nZSB0aGVpciBudW1iZXJzIGZyb20gMSB0byBtLCBpbiB0aGUgc2FtZSBvcmRlciB3aXRoCiB0aGVpciBpbml0aWFsIG9uZS4gPGJyPgogIElmIHdlIGRpdmlkZSBvdXIgc3R1ZGVudHOhryBoZWlnaHRzIGludG8gayAoMTw9azw9MjUpIGxldmVsLCBleHBlcmllbmNlIHNheXMgdGhhdCB0aGVyZSB3aWxsIGV4aXN0IGFuIGJlc3Qgdmlld2luZyBtb2R1bGUsIHJlcHJlc2VudGVkIGJ5IGFuIGFycmF5IGFbXS4gYVtpXSAoMTw9aTw9bSlzdGFuZHMgZm9yIHRoZSBzdHVkZW50oa9zIGhlaWdodCB3aXRoIG51bWJlciBpLiBJbiBmYWN0LCBpbnNpZGUgYSBxdWV1ZSwgZm9yIGV2ZXJ5IG51bWJlciBwYWlyCiBpLCBqICgxPD1pLGo8PW0pLCBpZiB0aGUgcmVsYXRpdmUgYmlnZ2VyIG9yIHNtYWxsZXIgb3IgZXF1YWwgdG8gcmVsYXRpb25zaGlwIGJldHdlZW4gdGhlIGhlaWdodCBvZiBzdHVkZW50IG51bWJlciBpIGFuZCB0aGUgaGVpZ2h0IG9mIHN0dWRlbnQgbnVtYmVyIGogaXMgdGhlIHNhbWUgd2l0aCB0aGF0IGJldHdlZW4gYVtpXSBhbmQgYVtqXSwgdGhlbiB0aGUgcXVldWUgaXMgd2VsbCBkZXNpZ25lZC4gR2l2ZW4gbiBzdHVkZW50c6GvIGhlaWdodCBhcnJheQogeFtdICgxPD14W2ldPD1rKSwgYW5kIHRoZSBiZXN0IHZpZXdpbmcgbW9kdWxlIGFycmF5IGFbXSwgaG93IG1hbnkgd2VsbCBkZXNpZ25lZCBxdWV1ZXMgY2FuIHdlIG1ha2UgYXQgbW9zdD88YnI+CgoKIAo8YnI+CgpJbnB1dAoKTXVsdGlwbGUgY2FzZXMsIGVuZCB3aXRoIEVPRi48YnI+CkZpcnN0IGxpbmUsIDMgaW50ZWdlcnMsIG4gKDE8PW48PTEwXjUpIG0gKDE8PW08PW4pIGsoMTw9azw9MjUpLDxicj4KU2Vjb25kIGxpbmUsIG4gc3R1ZGVudHOhryBoZWlnaHQgYXJyYXkgeFtdICgxPD14W2ldPD1rLDE8PWk8PW4pOzxicj4KVGhpcmQgbGluZSwgbSBpbnRlZ2VycywgYmVzdCB2aWV3aW5nIG1vZHVsZSBhcnJheSBhW10gKDE8PWFbaV08PWssMTw9aTw9bSk7PGJyPgoKCiAKPGJyPgoKT3V0cHV0CgpPbmUgaW50ZWdlciwgdGhlIG1heGltYWwgYW1vdW50IG9mIHdlbGwgZGVzaWduZWQgcXVldWVzLjxicj4KCgogCjxicj4KClNhbXBsZSBJbnB1dAoKPHByZSBjbGFzcz0="brush:java;">10 5 10 2 4 2 4 2 4 2 4 2 4 1 2 1 2 1
Sample Output

1

KMP的變形題，關鍵在於處理相對高度這個問題。

一個個匹配過去，如果前綴匹配，並且加上當前字母後，前面比這個字母小的，相等的，大於的數字個數都相等，就是匹配，剩下的就是KMP了。

代碼：

#include 
#include 

const int N = 100005;
const int M = 26;
int n, m, k, seq[N], seq1[N], next[N], i, t, sum1[M][N], sum2[M][N];

bool judge(int i, int j, int sum1[][N], int sum2[][N], int *seq, int *seq1) {
	int eq1 = 0, lt1 = 0, eq2 = 0, lt2 = 0;
	for (int x = 1; x <= k; x++) {
		if (x < seq[i]) {
			lt1 += sum1[x][i] - sum1[x][i - j];
		}
		else if (x == seq[i]) {
			eq1 += sum1[x][i] - sum1[x][i - j];
		}
		if (x < seq1[j]) {
			lt2 += sum2[x][j];
		}
		else if (x == seq1[j]) {
			eq2 += sum2[x][j];
		}
	}
	return (lt1 == lt2 && eq1 == eq2);
}

void get_next(int *seq, int m) {
	memset(next, 0, sizeof(next));
	int j = 0;
	for (int i = 2; i <= m; i++) {
		while (j > 0 && !judge(i, j + 1, sum2, sum2, seq1, seq1))
			j = next[j];
		if (judge(i, j + 1, sum2, sum2, seq1, seq1)) j++;
		next[i] = j;
	}
}

int kmp(int *seq, int *seq1, int n, int m) {
	int j = 0, ans = 0;
	for (int i = 1; i <= n; i++) {
		while (j > 0 && !judge(i, j + 1, sum1, sum2, seq, seq1)) j = next[j];
		if (judge(i, j + 1, sum1, sum2, seq, seq1)) j++;
		if (j == m) {
			ans++;
			j = 0;
		}
	}
	return ans;
}

int main() {
	while (~scanf("%d%d%d", &n, &m, &k)) {
		memset(sum1, 0, sizeof(sum1));
		memset(sum2, 0, sizeof(sum2));
		for (i = 1; i <= n; i++) {
			scanf("%d", &seq[i]);
			for (int j = 1; j <= k; j++)
				sum1[j][i] = sum1[j][i - 1];
			sum1[seq[i]][i]++;
		}
		for (i = 1; i <= m; i++) {
			scanf("%d", &seq1[i]);
			for (int j = 1; j <= k; j++)
				sum2[j][i] = sum2[j][i - 1];
			sum2[seq1[i]][i]++;
		}
		get_next(seq1, m);
		printf("%d\n", kmp(seq, seq1, n, m));
	}
	return 0;
}