Codeforces Round #215 (Div. 1) B. Sereja ans Anagrams
解法
配列 a の s 〜 s+p*(m-1) にある, p 個おきの 配列 b の要素数を数えます。
この要素数が b の要素数と一致していれば嬉しいですが, これを高速に数えたいです。
これは, 蟻本の p137, p138 に書いてある問題と似ています。
cnt[i] = (配列 b の i 番目に小さい要素が考えている区間に含まれている数), target[i] = (配列 b の i 番目に小さい要素が含まれている数(配列 b の考える区間は変わらないので, これは一定)), num = (cnt[i] >= target[i] を満たす i の数) として, 配列 a の m 個の要素で num の数が配列 b の異なる要素の数に一致すれば, s からの m 要素は b と一致させることが出来ます。
const int MAXN = 200200; int a[MAXN], b[MAXN]; int main() { int n, m, p; cin >> n >> m >> p; map<int, int> mp; for (int i = 0; i < n; i++) { scanf("%d", a+i); } for (int i = 0; i < m; i++) { scanf("%d", b+i); mp[b[i]] = 0; } vector<int> ans; int k = 0; for (auto& p : mp) p.second = k++; vector<int> target(k); for (int i = 0; i < m; i++) target[mp[b[i]]]++; for (int i = 0; i < p; i++) { if (i+(ll)(m-1)*p >= n) continue; int num = 0; vector<int> cnt(k); for (int j = 0; j < m; j++) { if (mp.find(a[i+j*p]) != mp.end()) { int index = mp[a[i+j*p]]; if (++cnt[index] == target[index]) num++; } } if (num == k) ans.push_back(i); for (int j = m; i+j*p < n; j++) { if (mp.find(a[i+(j-m)*p]) != mp.end()) { int index = mp[a[i+(j-m)*p]]; if (cnt[index]-- == target[index]) num--; } if (mp.find(a[i+j*p]) != mp.end()) { int index = mp[a[i+j*p]]; if (++cnt[index] == target[index]) num++; } if (num == k) ans.push_back(i+(j-m+1)*p); } } sort(ans.begin(), ans.end()); cout << ans.size() << endl; for (int el : ans) printf("%d ", el+1); printf("\n"); return 0; }