Cod sursa(job #1781801)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 17 octombrie 2016 14:46:44
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

const int kMaxN = 2000000;

int skip[256];
char a[kMaxN + 1], b[kMaxN + 1];

int main() {
	ifstream cin("strmatch.in");
	ofstream cout("strmatch.out");
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> a >> b; n = strlen(a); m = strlen(b);

	for (int i = 0; i < 256; i += 1) {
		skip[i] = 0x100;
	}
	for (int i = 0; i < n; i += 1) {
		skip[(int)a[i]] = n - i;
	}
	
	vector<int> occurences;
	int remainingOccurences = 0;
	for (int i = 0; i <= m - n; i += skip[(int)b[i + n]]) {
		if (not memcmp(a, b + i, n)) {
			if (SZ(occurences) < 1000) {
				occurences.emplace_back(i);
			} else {
				remainingOccurences += 1;
			}
		}
	}

	cout << SZ(occurences) + remainingOccurences << '\n';
	for (const int &idx : occurences) {
		cout << idx << ' ';
	}
	cout << '\n';
	return 0;
}