Cod sursa(job #827648)

Utilizator VincentVegaVincent Vega VincentVega Data 2 decembrie 2012 13:33:16
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define NMAX 2000100

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");


int solution[1011];

char A[NMAX], B[NMAX];
int length1, length2;


int main()
{
	
	int hash_num = 3;
	int key[] = {0, 10107, 10119, 10103};
	int base[] = {0, 22, 22, 22};
	int codeA[] = {0, 0, 0, 0};
	int codeB[] = {0, 0, 0, 0};
	int P[100] = {0, 1, 1, 1};
	
	fin >> A >> B;
	length1 = strlen(A);
	length2 = strlen(B);
	
	if (length1 > length2)
	{
		fout << "0\n";
		return 0;
	}
	
	for (int i = 0; i < length1; ++i)
	{
		for (int j = 1; j <= hash_num; ++j)
		{
			codeA[j] = codeA[j] * base[j] + A[i] - '0';
			codeB[j] = codeB[j] * base[j] + B[i] - '0';
			codeA[j] %= key[j];
			codeB[j] %= key[j];
			
			if (i > 0) P[j] *= base[j];
			P[j] %= key[j];
		}
	}
	
	for (int i = length1; i <= length2; ++i)
	{
		bool ok = true;
		
		for (int j = 1; j <= hash_num && ok; ++j)
		{
			if (codeA[j] != codeB[j]) ok = false;
		}
		
		if (ok)
		{
			if (solution[0] < 1000)
			{
				solution[++solution[0]] = i - length1;
			}
			else solution[0]++;
		}
		
		for (int j = 1; j <= hash_num; ++j)
		{
			codeB[j] = base[j] * (codeB[j] - P[j] * (B[i - length1] - '0')) + B[i] - '0';
			codeB[j] %= key[j];
			if (codeB[j] < 0) codeB[j] += key[j];
		}
	}
	
	fout << solution[0] << '\n';
	for (int i = 1; i <= min(solution[0], 1000); ++i)
	{
		fout << solution[i] << ' ';
	}
	
	fout.close();
	return 0;
}