Cod sursa(job #719239)

Utilizator marius135Dumitran Adrian Marius marius135 Data 21 martie 2012 17:29:47
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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>

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

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) {
			sol[nr++] = i - j;
			j = rez[j];
		}
	}
	return nr;
}

int main() {
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	cin>>sir1>>sir2;
	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;
}