Cod sursa(job #1737670)

Utilizator AplayLazar Laurentiu Aplay Data 4 august 2016 16:10:00
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

#define MAXN 2000010
#define pb push_back

using namespace std;

char A[MAXN], B[MAXN];
int n, m, F[MAXN], ans;
vector<int> matches;

void failFunction(char* S, int length) {
	int j;
	
	F[0] = F[1];
	
	for (int i = 2; i <= length; ++i) {
		j = F[i - 1];
		
		for ( ; ; ) {
			if (S[j] == S[i - 1]) {
				F[i] = j + 1;
				break;
			}
			
			if (j == 0) {
				F[i] = 0;
				break;
			}
			
			j = F[j];
		}
	}
}

void kmp(char* A, int m, char* B, int n, int* F) {
	int i = 0, j = 0;
	
	while(1) {
		if (j == n) break;
		
		if (A[i] == B[j]) {
			++i;
			++j;
			if (i == m) {
				++ans;
				matches.pb(j - m);
				i = F[i];
				if (ans == 1000) return;
			}
		}
		else {
			if (i == 0) {
				++j;
			}
			else {
				i = F[i];
			}
		}
	}
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s\n%s", A, B);
	
	m = strlen(A);
	n = strlen(B);
	
	if (m > n) printf("0");
	else {
		failFunction(A, m);
		kmp(A, m, B, n, F);
	}
	
	printf("%d\n", ans);
	for (int i = 0; i < matches.size(); ++i)
		printf("%d ", matches[i]);
	
	return 0;
}