Cod sursa(job #774531)

Utilizator prisonbreakMichael Scofield prisonbreak Data 5 august 2012 16:46:26
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>

const int maxn = 2000005;

using namespace std;

int n, m;
char a[maxn], b[maxn];
int perm[maxn], sol[maxn];

inline void swap(int &a, int &b) {
	int aux = a; a = b; b = aux;
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	scanf("%s\n%s\n", a , b);
	n = strlen(a); m = strlen(b);

	//let's try more of a randomized matching

	srand(time(NULL));
	
	for(int i = 0; i < n; ++i)
		perm[i] = i;

	for(int i = 0; i < m - n; ++i) {
		
		int j;
		for(j = 0; j < n; ++j) {
			int pos = rand() % (n - j + 1);
			
			if(a[perm[pos]] != b[i + perm[pos]]) break;
			swap(perm[pos], perm[n - j]);
		}
		if(j == n) {
			sol[++sol[0]] = i;
		}
	}
	
	printf("%d\n", sol[0]);
	
	for(int i = 1; i <= min(1000, sol[0]); ++i)
		printf("%d ", sol[i]);
	
	return 0;
}