Cod sursa(job #2411601)

Utilizator stoianmihailStoian Mihail stoianmihail Data 20 aprilie 2019 21:37:30
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.47 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <cassert>
#include <iostream>

using namespace std;

typedef vector<int> VI;
const double PI = acos(0) * 2;
const unsigned MAX_SIZE = 1000;

class complex
{
public:
	double a, b;
	complex() {a = 0.0; b = 0.0;}
	complex(double na, double nb) {a = na; b = nb;}
	const complex operator+(const complex &c) const
		{return complex(a + c.a, b + c.b);}
	const complex operator-(const complex &c) const
		{return complex(a - c.a, b - c.b);}
	const complex operator*(const complex &c) const
		{return complex(a*c.a - b*c.b, a*c.b + b*c.a);}
	double magnitude() {return sqrt(a*a+b*b);}
	void print() {printf("(%.3f %.3f)\n", a, b);}
};

class FFT
{
public:
	vector<complex> data;
	vector<complex> roots;
	VI rev;
	int s, n;

	void setSize(int ns)
	{
		s = ns;
		n = (1 << s);
		int i, j;
		rev = VI(n);
		data = vector<complex> (n);
		roots = vector<complex> (n+1);
		for (i = 0; i < n; i++)
			for (j = 0; j < s; j++)
				if ((i & (1 << j)) != 0)
					rev[i] += (1 << (s-j-1));
		roots[0] = complex(1, 0);
		complex mult = complex(cos(2*PI/n), sin(2*PI/n));
		for (i = 1; i <= n; i++)
			roots[i] = roots[i-1] * mult;
	}

	void bitReverse(vector<complex> &array)
	{
		vector<complex> temp(n);
		int i;
		for (i = 0; i < n; i++)
			temp[i] = array[rev[i]];
		for (i = 0; i < n; i++)
			array[i] = temp[i];
	}

	void transform(bool inverse = false)
	{
		bitReverse(data);
		int i, j, k;
		for (i = 1; i <= s; i++) {
			int m = (1 << i), md2 = m / 2;
			int start = 0, increment = (1 << (s-i));
			if (inverse) {
				start = n;
				increment *= -1;
			}
			complex t, u;
			for (k = 0; k < n; k += m) {
				int index = start;
				for (j = k; j < md2+k; j++) {
					t = roots[index] * data[j+md2];
					index += increment;
					data[j+md2] = data[j] - t;
					data[j] = data[j] + t;
				}
			}
		}
		if (inverse)
			for (i = 0; i < n; i++) {
				data[i].a /= n;
				data[i].b /= n;
			}
	}

	static VI convolution(VI &a, VI &b)
	{
		int alen = a.size(), blen = b.size();
		int resn = alen + blen - 1;	// size of the resulting array
		int s = 0, i;
		while ((1 << s) < resn) s++;	// n = 2^s
		int n = 1 << s;	// round up the the nearest power of two

		FFT pga, pgb;
		pga.setSize(s);	// fill and transform first array
		for (i = 0; i < alen; i++) pga.data[i] = complex(a[i], 0);
		for (i = alen; i < n; i++)	pga.data[i] = complex(0, 0);
		pga.transform();

		pgb.setSize(s);	// fill and transform second array
		for (i = 0; i < blen; i++)	pgb.data[i] = complex(b[i], 0);
		for (i = blen; i < n; i++)	pgb.data[i] = complex(0, 0);
		pgb.transform();

		for (i = 0; i < n; i++)	pga.data[i] = pga.data[i] * pgb.data[i];
		pga.transform(true);	// inverse transform
		VI result = VI (resn);	// round to nearest integer
		for (i = 0; i < resn; i++)	result[i] = (int) (pga.data[i].a + 0.5);

		int actualSize = resn - 1;	// find proper size of array
		while (result[actualSize] == 0)
			actualSize--;
		if (actualSize < 0) actualSize = 0;
		result.resize(actualSize+1);
		return result;
	}
};

unsigned square(uint32_t x) {
  return x * x;
}

int main(void) {
  ifstream in("strmatch.in");
  ofstream out("strmatch.out");

  string pattern, text;

  in >> pattern >> text;
  unsigned needlelen = pattern.size();
  VI p(needlelen);
  for (unsigned index = 0; index < needlelen; index++)
    p[needlelen - index - 1] = pattern[index] - 'A';
  unsigned size = text.size();
  VI s(size);
  for (unsigned index = 0; index < size; index++)
    s[index] = text[index] - 'A';

  long unsigned constPattern = 0;
  for (unsigned index = 0; index < needlelen; index++)
    constPattern += square(p[index]);

  long unsigned sums = 0;
  for (unsigned index = 0; index < needlelen - 1; index++)
    sums += square(s[index]);

  // Apply only for s and p.
  VI ret = FFT::convolution(s, p);

  // Shift the window at every step.
  int* matches = new int[MAX_SIZE];
  unsigned noMatches = 0;
  for (unsigned i = 0; i < size - needlelen + 1; i++) {
    sums += square(s[needlelen + i - 1]);
    if ((ret[i + needlelen - 1] << 1) == constPattern + sums) {
      if (++noMatches <= MAX_SIZE)
        matches[noMatches - 1] = i;
    }
    sums -= square(s[i]);
  }

  // Print the results.
  out << noMatches << "\n";
  noMatches = (noMatches <= MAX_SIZE) ? noMatches : MAX_SIZE;
  for (unsigned index = 0; index < noMatches; ++index)
    out << matches[i] << " ";
  return 0;
}