Cod sursa(job #719247)

Utilizator marius135Dumitran Adrian Marius marius135 Data 21 martie 2012 17:35:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
// Martie 2012 Dumitran Marius
// KMP O(n+m)
// Infoarena Arhiva Educationala Potrivirea Sirurilor 

// Infoarena - Arhiva Educationala Potrivirea Sirurilor 
// Februrie 2012 Marius Dumitran
// Rabin Karp O(n+m)

#include<string>
#include<iostream>
#include<stdio.h>

using namespace std;
#define maxn (1<<21)

char sir3[maxn], sir4[maxn];
string sir1, sir2;
int sol[ 2000 ], nr = 0;
int rez[maxn];
void prekmp( string sir, int * rez) {
	
	
	int n = sir.size(), i = 0, j = -1;
	rez[0] = -1;
	while( i < n ) {
		while( j >= 0 && sir[i] != sir[j]) // daca elementele nu sunt compatibile si nu am ajuns inca la inceput
			j = rez[j]; // j ia urmataorea valoare posibila
		i++; j++;
		rez[i] = j;
	}
}
int kmp( string sir1, string sir2, int *rez) {
	int i = 0, j = 0;
	int n = sir1.size(), m = sir2.size();
	while (i < n ) {
		while(j >= 0 && sir1[i] != sir2[j]) 
			j = rez[j];
		i++; j++;
		if( j == m) {
			if( nr < 1500)
				sol[nr++] = i - j;	
			j = rez[j];
		}
	}
	return nr;
}

int main() {
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s %s", sir3, sir4);
	sir1 = sir3;
	sir2 = sir4;
	int n = sir1.size(), m = sir2.size();

	if( n > m )	{
		printf("0\n"); 
		return 0;
	}
	
	prekmp(sir1, rez);
	
	
	printf("%d\n", kmp(sir2,sir1, rez));
	for( int i = 0; i < nr && i < 1000; ++i)
		printf("%d ", sol[i]);
	printf("\n");

 
	
	return 0;
}