Cod sursa(job #182073)

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

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


char a[2000896], b[2000896];


long long rotate(long long v, int n)
{
	return (v << n) | (v >> (64 - n));
}


char make(int k)
{
	if ('A' <= k && k <= 'Z')
		return k - 'A';
	return k - 'a' + 'Z';
}


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;
	}

	long long ha = 0, hb = 0;
	for (int i = 0; i < la; i++)
	{
		ha = rotate(ha, 3) ^ make(a[i]);
		hb = rotate(hb, 3) ^ make(b[i]);
	}


	vector<int> sol;
	if (ha == hb)
		sol.push_back(0);

	for (int i = la; i < lb; i++)
	{
		hb ^= rotate((int)make(b[i - la]), ((la - 1) * 3) % 64);
		hb = rotate(hb, 3) ^ make(b[i]);

		if (ha == hb)
			sol.push_back(i - la + 1);
	}


	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;
}