Cod sursa(job #1241037)

Utilizator sorin2kSorin Nutu sorin2k Data 12 octombrie 2014 15:14:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

int pi[2000001];
char a[2000002], b[2000002];
int ans[1005], nr, la, lb;

// k = cate caractere am potrivit (de la 0 la k-1)
void prefix() {
	int i, k = 0;
	for(i = 1; i < la; i++) {
		while(k > 0 && a[i] != a[k]) {
			k = pi[k-1];
		}
		if(a[i] == a[k]) {
			k++;
		}
		pi[i] = k;
	}
}

void match() {
	int i, k = 0;
	for(i = 0; i < lb; i++) {
		while(k > 0 && b[i] != a[k]) {
			k = pi[k-1];
		}
		if(b[i] == a[k]) {
			k++;
		}
		if(k == la) {
			if(nr < 1000) {
				ans[nr] = i-k+1;
			}
			nr++;
			k = pi[k-1];
		}
	}
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	int i, to;
	scanf("%s %s", a, b);
	la = strlen(a);
	lb = strlen(b);
	prefix();
	match();
	printf("%d\n", nr);
	to = (nr > 1000) ? 1000 : nr;
	for(i = 0; i < to; i++) {
		printf("%d ", ans[i]);
	}
	return 0;
}