Cod sursa(job #182192)

Utilizator Spike7d8Cristian Varvara Spike7d8 Data 20 aprilie 2008 14:33:32
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#ifdef WIN32
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

#define ROL(v, n) (v << n) | (v >> (32 - n))
#define B1 9
#define B2 11
char a[2000896], b[2000896];


int main()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);

	scanf("%s\n%s\n", a, b);
	int la = strlen(a), lb = strlen(b);

	if (la > lb)
	{
		printf("0\n");
		return 0;
	}

	int a1 = 0, a2 = 0;
	int b1 = 0, b2 = 0;
	for (int i = 0; i < la; i++)
	{
		a1 = ROL(a1, B1) ^ a[i];
		a2 = ROL(a2, B2) ^ a[i];

		b1 = ROL(b1, B1) ^ b[i];
		b2 = ROL(b2, B2) ^ b[i];
	}


	vector<int> sol;
	if (a1 == b1 && a2 == b2)
		sol.push_back(0);

	int r1 = (B1 * (la - 1)) % 32;
	int r2 = (B2 * (la - 1)) % 32;
	for (int i = la; i < lb; i++)
	{
		b1 ^= ROL(b[i - la], r1);
		b2 ^= ROL(b[i - la], r2);

		b1 = ROL(b1, B1) ^ b[i];
		b2 = ROL(b2, B2) ^ b[i];

		if (a1 == b1 && a2 == b2)
		{
			sol.push_back(i - la + 1);
			if (sol.size() == 1000)
				break;
		}
	}


	if (sol.size() == 0)
		printf("0\n");
	else
	{
		printf("%d\n", sol.size());
		for (int i = 0; i < (int)sol.size(); i++)
			printf("%d ", sol[i]);
		printf("\n");
	}

	return 0;
}