KMP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <stack>
 9 #include <map>
10 #include <set>
11 #include <cmath>
12 #include <cctype>
13 #include <ctime>
14 
15 using namespace std;
16 
17 #define REP(i, n) for (int i = 0; i < (n); ++i)
18 #define eps 1e-9
19 
20 typedef long long ll;
21 typedef pair<int, int> pii;
22 
23 const int INF = 0x7fffffff;
24 const int maxn = 1e5 + 10;
25 int n, k, s, ans_cnt = 0;
26 int fail[maxn], key_p1[maxn], key_p2[maxn], a[maxn], b[maxn], cnt[40], ans[maxn];
27 
28 inline int cal1(int x) {
29     int ret = 0;
30     for (int i = 1; i < x; ++i) { ret += cnt[i]; }
31     return ret;
32 }
33 inline int cal2(int x) { return cnt[x]; }
34 void init() {
35     for (int i = 0; i < k; ++i) {
36         key_p1[i] += cal1(b[i]); key_p2[i] += cal2(b[i]); ++cnt[b[i]];
37     }
38 }
39 void get_fail() {
40     memset(cnt, 0, sizeof(cnt));
41     fail[0] = fail[1] = 0; int j, t;
42     for (int i = 1; i < k; ++i) {
43         j = fail[i];
44         while (j && (cal1(b[i]) != key_p1[j] || cal2(b[i]) != key_p2[j])) {
45             t = j - fail[j]; j = fail[j];
46             for (int i_t = 0; i_t < t; ++i_t) { --cnt[b[i - j - i_t - 1]]; }
47         }
48         if (key_p1[j] == cal1(b[i]) && key_p2[j] == cal2(b[i])) { fail[i + 1] = j + 1; ++cnt[b[i]]; }
49         else { fail[i + 1] = 0; }
50     }
51 }
52 void kmp() {
53     get_fail(); int j = 0, t; memset(cnt, 0, sizeof(cnt));
54     for (int i = 0; i < n; ++i) {
55         while (j && (cal1(a[i]) != key_p1[j] || cal2(a[i]) != key_p2[j])) {
56             t = j - fail[j]; j = fail[j];
57             for (int i_t = 0; i_t < t; ++i_t) { --cnt[a[i - j - i_t - 1]]; }
58         }
59         if (key_p1[j] == cal1(a[i]) && key_p2[j] == cal2(a[i])) { ++j; ++cnt[a[i]]; }
60         if (j == k) {
61             ans[ans_cnt++] = i - k + 2;
62             t = j - fail[j]; j = fail[j];
63             for (int i_t = 0; i_t < t; ++i_t) {
64                 --cnt[a[i - j - i_t]];
65             }
66         }
67     }
68 }
69 
70 int main() {
71 #ifdef __AiR_H
72     freopen("in.txt", "r", stdin);
73 //    freopen("out.txt", "w", stdout);
74 #endif // __AiR_H
75     scanf("%d %d %d", &n, &k, &s);
76     for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); }
77     for (int i = 0; i < k; ++i) { scanf("%d", &b[i]); }
78     if (k > n) { printf("0
"); return 0; }
79     init(); kmp();
80     printf("%d
", ans_cnt);
81     for (int i = 0; i < ans_cnt; ++i) { printf("%d
", ans[i]); }
82 #ifdef __AiR_H
83     printf("Time used = %.2fs
", (double)clock() / CLOCKS_PER_SEC);
84 #endif // __AiR_H
85     return 0;
86 }
View Code