学步园

RT

这个题是POJ3167的修改版，基本一致

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 100005; 
int x[N], a[N], nex[N]; 
int pr1[N][30], pr2[N][30], n, m, s; 
void init() {
    memset(pr1, 0, sizeof(pr1)); 
    memset(pr2, 0, sizeof(pr2)); 
    pr1[1][x[1]] = pr2[1][a[1]] = 1; 
    for(int i = 2; i <= n; i++) {
        memcpy(pr1[i], pr1[i-1], sizeof(pr1[0])); 
        pr1[i][x[i]]++; 
    }
    for(int i = 2; i <= m; i++) {
        memcpy(pr2[i], pr2[i-1], sizeof(pr2[0])); 
        pr2[i][a[i]]++; 
    }
}
void getnex() {
    memset(nex, 0, sizeof(nex)); 
    int i = 1, j = 0, k, si, sj, ei, ej; 
    nex[1] = 0; 
    while(i <= m) {
        si = sj = ei = ej = 0; 
        for(k = 1; k < a[i]; k++)
            si += pr2[i][k]-pr2[i-j][k]; 
        ei = pr2[i][k]-pr2[i-j][k]; 
        for(k = 1; k < a[j]; k++)
            sj += pr2[j][k]; 
        ej = pr2[j][k]; 
        if(j == 0||(si == sj&&ei == ej))
            i++, j++, nex[i] = j; 
        else j = nex[j]; 
    }
}
void gao() {
    int i, j, k, si, sj, ei, ej, pre = -1, num = 0; 
    for(i = j = 1; i <= n; ) {
        si = sj = ei = ej = 0; 
        for(k = 1; k < x[i]; k++)
            si += pr1[i][k]-pr1[i-j][k]; 
        ei = pr1[i][k]-pr1[i-j][k]; 
        for(k = 1; k < a[j]; k++)
            sj += pr2[j][k]; 
        ej = pr2[j][k]; 
        if(j == 0||(si == sj&&ei == ej))
            i++, j++; 
        else j = nex[j]; 
        if(j == m+1) {
            if (i - 1 - m >= pre) {
                num ++; 
                pre = i - 1; 
            }
            j = nex[j]; 
        }
    }
    printf("%d\n", num); 
}
int main() {
    while(scanf("%d%d%d", &n, &m, &s) != EOF) {
        for(int i = 1; i <= n; i++)
            scanf("%d", &x[i]); 
        for(int i = 1; i <= m; i++)
            scanf("%d", &a[i]); 
        init(); 
        getnex(); 
        gao(); 
    }
    return 0; 
}