Cod sursa(job #827636)

Utilizator VincentVegaVincent Vega VincentVega Data 2 decembrie 2012 13:12:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define NMAX 2000100
#define key1 100007
#define key2 100021
#define base1 73
#define base2 73

using namespace std;

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


int solution[1011];
char A[NMAX], B[NMAX];
int length1, length2;
int code_A1, code_A2;
int code_B1, code_B2;
int P1 = 1, P2 = 1;


int main()
{
	fin >> A >> B;
	length1 = strlen(A);
	length2 = strlen(B);
	
	if (length1 > length2)
	{
		fout << "0\n";
		return 0;
	}
	
	for (int i = 0; i < length1; ++i)
	{
		code_A1 = code_A1 * base1 + A[i];
		code_A2 = code_A2 * base2 + A[i];
		
		code_B1 = code_B1 * base1 + B[i];
		code_B2 = code_B2 * base2 + B[i];
		
		code_A1 %= key1;
		code_A2 %= key2;
		
		code_B1 %= key1;
		code_B2 %= key2;
		
		if (i > 0)
		{
			P1 = P1 * base1;
			P2 = P2 * base2;
		}
		
		P1 %= key1;
		P2 %= key2;
	}
	
	for (int i = length1; i <= length2; ++i)
	{
		if (code_A1 == code_B1 && code_A2 == code_B2)
		{
			if (solution[0] < 1000)
			{
				solution[++solution[0]] = i - length1;
			}
			else break;
		}
		
		code_B1 = base1 * (code_B1 - P1 * (B[i - length1])) + B[i];
		code_B2 = base2 * (code_B2 - P2 * (B[i - length1])) + B[i];
		
		code_B1 %= key1;
		code_B2 %= key2;
		
		if (code_B1 < 0) code_B1 += key1;
		if (code_B2 < 0) code_B2 += key2;
	}
	
	fout << solution[0] << '\n';
	for (int i = 1; i <= solution[0]; ++i)
	{
		fout << solution[i] << ' ';
	}
	
	fout.close();
	return 0;
}