hdu 4749 Parade Show(KMP)

题目链接：hdu 4749 Parade Show

题目大意：学校要举办一场典礼，要从n个学生中选若干支队伍来，每支队伍有m个人。然后现在将学生的身高划分成k个等级，接着按照学生的顺序给出学生的身高等级，再然后，给出m个人的队伍要求的相对高度。然后要求从n个中间挑选连续的m个人，满足相对高度即可组成一支队伍。问说最多可以组成多少支队伍。

解题思路：KMP算法的变形，只不过在判断相等的时候有点难办，因为它算的是相对高度，就是同一支队伍中，对应比自己高的个数，相等的个数，比自己矮的个数都要和要求的相等，所以要开一个cx，cy数组，将KMP中判断相等写成一个函数。

#include <stdio.h>
#include <string.h>

const int N = 1e5+5;
int n, m, k, next[N], x[N], y[N];
int cx[N][30], cy[N][30];

void init () {
    int a;

	memset(cx[0], 0, sizeof(cx[0]));
	memset(cy[0], 0, sizeof(cy[0]));

    for (int i = 1; i <= n; i++) {
		memcpy(cx[i], cx[i-1], sizeof(cx[i-1]));
        scanf("%d", &x[i]);
		cx[i][x[i]]++;
    }

    for (int i = 1; i <= m; i++) {
		memcpy(cy[i], cy[i-1], sizeof(cy[i-1]));
        scanf("%d", &y[i]);
		cy[i][y[i]]++;
    }
}

bool judge (int p, int q, int (*a)[30], int (*b)[30], int tp, int tq) {
	int s = 0;
	for (int i = 1; i < tp; i++)
		s += a[p][i];
	for (int i = 1; i < tq; i++)
		s -= (b[q][i] - b[q-p][i]);
	return s == 0 && a[p][tp] == (b[q][tq] - b[q-p][tq]);
}

void getNext () {
    int j = 0;
    for (int i = 2; i <= m; i++) {
        while (j > 0 && !judge (j+1, i, cy, cy, y[j+1], y[i]))
            j = next[j];

        if (judge (j+1, i, cy, cy, y[j+1], y[i]))
            j++;
        next[i] = j;
    }
}

int KMP () {
    int ans = 0;
    getNext();

    int j = 0;
    for (int i = 1; i <= n; i++) {
        while (j > 0 && !judge (j+1, i, cy, cx, y[j+1], x[i]))
            j = next[j];

        if (judge (j+1, i, cy, cx, y[j+1], x[i]))
            j++;

        if (j == m) {
            ans++;
            j = 0;
        }
    }
    return ans;
}

int main () {
    while (scanf("%d%d%d", &n, &m, &k) == 3) {
        init ();
        printf("%d\n", KMP());
    }
    return 0;
}

hdu 4749 Parade Show(KMP),布布扣,bubuko.com

hdu 4749 Parade Show(KMP)

原文：http://blog.csdn.net/keshuai19940722/article/details/21339045