7038번: Cow Patterns

https://www.acmicpc.net/problem/7038

$O((n+k)s^2)$

#include<cstdio>
const int MXN = 1e5, MXK = 25e3;
int n, k, s, a[26][MXN + 1], b[26][MXK + 1], ck[26], maxi[MXN + 1], cnt[MXN + 1], pi[MXK + 2], t, r;
void kmp(int *c, int *p, int x) {
    for (int i = 1, j = 0; i <= k;) {
        if (!j || p[i] == p[j]) pi[++i] = ++j;
        else j = pi[j];
    }
    for (int i = 1, j = 1; i <= n;) {
        if (!j || c[i] == p[j]) i++, j++;
        else j = pi[j];
        if (j > k) {
            j = pi[j];
            if (maxi[i - k] < x) {
                maxi[i - k] = x;
                r += ++cnt[i - k] == t;
            }
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &k, &s);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), a[x][i]++;
    for (int i = 1, x; i <= k; i++) scanf("%d", &x), b[x][i]++, ck[x] = 1;
    for (int i = 1; i <= s; i++) t += ck[i];
    for (int i = 1; i <= s; i++) if (ck[i]) {
        for (int j = 1; j <= s; j++) kmp(a[j], b[i], j);
    }
    printf("%d", r);
    for (int i = 1; i <= n; i++) if (cnt[i] == t) printf("\n%d", i);
    return 0;
}