Cod sursa(job #154573)

Utilizator plastikDan George Filimon plastik Data 11 martie 2008 12:06:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.38 kb
#include <cstdio>
#include <cstring>
#define MAXN 2000005
#define MAXP 1024

char Text[MAXN], Word[MAXN];
int Pi[MAXN], Match[MAXP];

void KMPFailureFunction() {
	// Pi[i] = lungimea celui mai mare prefix care e si sufix
	// al prefixului de lungime i din cuvant (0..i-1)
	
	// abc***abc????????
	// Pi[9] = 3
	
	Pi[0] = -1;
	Pi[1] = 0; // ne intereseaza doar prefixe proprii
	
	int i, k, n = strlen(Word);
	// i = lungimea pentru care calculez Pi[i]
	// k = lungimea prefixului la sfarsitul caruia vreau sa adaug 
	// caracterul i - 1
	
	// Calculez pentru lungimea i
	// S = Word
	
	// <---------------------i------------------------->
	 
	// -------------------------------------------------
	// | +++++++    +++++++         +++++++    +++++++ | 
	// | +abc  +Z???+  abc+Y  ...   +abc  +????+  abc+ |X
	// | +++++++    +++++++         +++++++    +++++++ |
	// -------------------------------------------------
	//											 X = S(i - 1) - al i-lea element
	//				 Y = S(k) - indexare de la 0 (al k + 1-lea element)
	//  <--------k-------->
	//  <-Pi[k]->
	
	// Initial incerc sa adaug X la prefixul maxim obtinut deja - lungimea lui e k
	// Pentru asta trebuie ca urmatorul caracter dupa secventa de k caractere intiala sa corespunda cu X
	// Celelalte k caractere de la inceput respectiv sfarsit corespund datorita 
	// definitiei lui k (lungime celui mai lung prefix care e si sufix)
	
	// Daca cele 2 caractere corespund, Pi[i] = k + 1 (Y-ul se poate inlocui cu X pe desen)
	
	// Daca cele 2 caractere nu corespund, inseamna ca cel mai lung prefix care e si sufix din primele i caractere
	// e mai scurt. Pentru a nu face verificari inutile observam ca:
	// Daca k e lungimea celui mai lung prefix care e si sufix din primele i - 1 caractere,
	// PREFIXUL PRIMELOR I CARACTERE ESTE SI PREFIX AL PRIMELOR K CARACTERE
	// SUFIXUL PRIMELOR I CARACTERE ESTE SI SUFIXUL ULTIMELOR K CARACTERE
	
	// De aceea, este importanta lungimea celui mai lung prefix care e si sufix al primelor k caractere
	// Valoarea este deja calculata - este Pi[k]
	// Urmatoarea comparatie va fi deci intre Z si X, Z = S(Pi[k]) - indexare de la 0
	// Daca Z != X, se repeta pasul cu Pi[Pi[k]] si tot asa pana cand, in cel mai rau caz nu corespund caractere deloc
	// Asta se intampla cand k = 0. In Acest caz, Pi[i] = 0
	
	// In momentul in care am aflat acel k pentru care caracterele sa se potriveasca, il vom creste cu 1
	// pentru ca acum, lungimea celui mai bun prefix care e si sufix este k + 1 (desen)
	
	for (i = 2, k = 0; i <= n; ++ i) {
		while (k > 0 && Word[i - 1] != Word[k]) // tot merg pe prefixe incercand sa gasesc Y-ul care sa fie egal cu X-ul
			k = Pi[k];
		if (Word[i - 1] == Word[k]) // daca il gasesc, lungimea perfixului care este si sufix este cu 1 mai mare
			++ k;
		Pi[i] = k;
	}

}

void KMPSearch() {
	int i, k, n = strlen(Word), m = strlen(Text);
	
	// exact ca la functia precedenta dar acum caracterul pe care vreau sa-l adaug
	// face parte din Text
	
	for (i = 1, k = 0; i <= m; ++ i) {
		while (k > 0 && Word[k] != Text[i - 1])
			k = Pi[k];
		if (Word[k] == Text[i - 1])
			++ k;
		if (k == n) {
			Match[++ Match[0]] = i - k;
			if (Match[0] == 1000)
				return;
		}
	}
}

int main() {

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

	scanf("%s\n%s", Word, Text);
	
	KMPFailureFunction();
	KMPSearch();
	
	printf("%d\n", Match[0]);
	for (int i = 1; i <= Match[0]; ++ i)
		printf("%d ", Match[i]);
	
	return 0;
}