Cod sursa(job #1146779)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 19 martie 2014 11:43:01
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

#define ideone
const int Max = 2 * 1000 * 1000 + 5;

char a[Max], b[Max];
int pref[Max];
int A, B;
int r, s[1005];

int main() {
	#ifndef ideone
		ifstream cin("strmatch.in");
		ofstream cout("strmatch.out");
	#endif
	
	cin >> (a + 1) >> (b + 1);
	A = strlen(a + 1); B = strlen(b + 1);
	
	for (int i = 2, q = 0; i <= A; ++i) {
		while (a[q + 1] != a[i] && q)
			q = pref[q];
		if (a[q + 1] == a[i])
			++q;
		pref[i] = q;
	}
	
	for (int i = 1, q = 0; i <= B; ++i) {
		while (a[q + 1] != b[i] && q)
			q = pref[q];
		if (a[q + 1] == b[i])
			++q;
		if (q == A) {
			++r;
			q = pref[q];
			if (r <= 1000)
				s[++s[0]] = i - A;
		}
	}
	
	cout << r << '\n';
	for (int i = 1; i <= s[0]; ++i)
		cout << s[i] << ' ';
	cout << '\n';
	return 0;
}