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; }
|