Cod sursa(job #1367598)

Utilizator paftenieAdrian Pop paftenie Data 1 martie 2015 23:22:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>
#include <string.h>

const int MAX = 2000001;
const long int MOD = 100007; // 3367900313; // 1299827; // 1000003;
const int BASE = 73;

char str[MAX], substr[MAX];

int matches[1001];
int nMatches;


void match (int position) {
	matches[nMatches] = position;
	nMatches++;
}

int main () {
	FILE *fin = freopen("strmatch.in", "rt", stdin);
	FILE *fout = freopen("strmatch.out", "wt", stdout);
	
	scanf("%s %s", substr, str);
	
	int substrLen = strlen(substr);
	int strLen = strlen(str);
	
	// ---
	long int substrHash = substr[0];
	long int pow = 1;
	
	for (int i = 1; i < substrLen; i++) {
		char front = substr[i];
		pow = (pow * BASE) % MOD;
		substrHash = (substrHash * BASE + front) % MOD;
		
	}
	//printf("pow %ld\n", pow);	
	//printf("substrHash %ld\n", substrHash);
	// ---
	long int candidateHash = 0;
	for (int i = 0; i < substrLen; i++) {
		char front =  str[i];
		candidateHash = (candidateHash * BASE + front) % MOD;
	}
		
	if (candidateHash == substrHash) {
		match(0);
	}
	
	// ---	
	for (int i = 0, j = substrLen; j < strLen && nMatches < 1000; i++, j++) {
		char back = str[i];
		char front = str[j];
		candidateHash = ((candidateHash - (back * pow) % MOD + MOD) * BASE + front) % MOD;
		//printf("candidateHash %ld substringHash %ld\n", candidateHash, substrHash);
		if (candidateHash == substrHash) {
			match(i + 1);
		}
	}
	
	// ---
	printf("%d\n", nMatches);
	for (int i = 0; i < nMatches; i++) {
		printf("%d ", matches[i]);
	}
	
	printf("\n");
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}