Cod sursa(job #1174523)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 23 aprilie 2014 09:39:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <vector>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <fstream>

using namespace std;

#define ONLINE_JUDGE

#define MOD1 666013
#define MOD2 666019
#define base 73

#define pb push_back
#define ENTER fprintf(output, "\n");
#define OKK fprintf(output, "ok!\n");
#define all(V) V.begin(), V.end()
#define allr(V) V.rbegin(), V.rend()
#define LL long long

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

char A[2000002], B[2000002];
int L[2000002];
int cnt;
vi ans;

void makePrefix(char *S) {
	int lgS = strlen(S), k;
	L[1] = 0;
	k = 0;
	for (int i = 2; i <= lgS; ++i) {
		while(k > 0 && A[k + 1] != A[i]) {
			k = L[k];
		}
		if (A[k + 1] == A[i]) {
			++k;
		}
		L[i] = k;
	}
}

int main() {
#ifdef ONLINE_JUDGE
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
#else
	freopen("input.txt", "r", stdin);
#endif
	int lgA, lgB, i, k;
	
	scanf("%s %s", A + 1, B + 1);
	
	lgA = strlen(A + 1);
	lgB = strlen(B + 1);
	
	makePrefix(A + 1);
	
	k = 0;
	for (i = 1; i <= lgB; ++i) {
		while (k > 0 && B[i] != A[k + 1]) {
			 k = L[k];
		}
		if (A[k + 1] == B[i]) {
			++k;
		}
		if (k == lgA) {
			k = L[lgA];
			++cnt;
			if (cnt < 1001) {
				ans.pb(i - lgA);
			}
		}
	}
	printf("%d\n", cnt);
	for (auto x: ans) {
		printf("%d ", x);
	}
 	return 0;
}