Rešenje grubom silom podrazumeva da se za svako moguće poravnavanje eksplicitno prebroje tačke koje se poklapaju. Složenost ovog rešenja je \(O(|s|\cdot |t|)\).
#include <iostream>
#include <string>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
for (int i = 0; i + t.length() <= s.length(); i++) {
int k = 0;
for (int j = 0; j < t.length(); j++)
if (s[i+j] == '.' && t[j] == '.')
k++;
cout << k << " ";
}
cout << endl;
}Kreirajmo binarne nizove \(S\) i \(T\) istih dužina kao niske \(s\) i \(t\), takve da je \(S_k = 1\) akko je s[k] == '.' i da je \(T_k = 1\) akko je t[k] == '.'. Razmotrimo poravnanje koje počinje na poziciji \(i\). Tada se broj tačaka koje se poklapaju može izračunati izrazom:
\[\sum_{j=0}^{|t|-1} S_{i+j}\cdot T_j.\]
Ovaj zbir je potrebno izračunati za svaku poziciju \(0 \leq i \leq |s| - |t|\). Operacija u kojoj se kraći niz pomera duž dužeg i računaju se zbirovi proizvoda elemenata na odgovarajućim pozicijama nazivaju se konvolucija i ona se jednostavno svodi na problem množenja polinoma.
Razmotrimo množenje polinoma \(P(x) = \sum_{i=0}^m a_ix^i\) i \(Q(x) = \sum_{j=0}^n b_jx^j\). Njihov proizvod je polinom:
\[P(x)Q(x) = \sum_{i=0}^m\sum_{j=0}^n a_ib_jx^{i+j}.\]
Grupišući koeficijente uz isti stepen broja \(x\) dobijamo:
\[P(x)Q(x)=\sum_{k=0}^{m+n}\left(\sum_{j=0}^k a_{k-j}b_j\right)x^k,\]
pri čemu podrazumevamo da je \(a_i=0\) za \(i \geq m\) i \(b_j = 0\) za \(j \geq n\). Fokusirajmo se na koeficijente uz stepene \(x^k\) za \(k\) između \(m-1\) i \(n-1\). Oni su jednaki:
\[\sum_{j=0}^{m-1} a_{k-j}b_j,\]
što liči na sume koje želimo da izračunamo konvolucijom, jedino što se elementi množe u obratnom redosledu (prvi element niza \(b\) množi sa poslednjim elementom odgovarajućeg dela niza \(a\), drugi sa pretposlednjim itd.). Jedna operacija se lako svodi na drugu obrtanjem redosleda koeficijenata jednog od polinoma. Uzmimo da je \(P(x) = \sum_{i=0}^{|s|-1} S_ix^i\), a da je \(Q(x) = \sum_{j=0}^{|t|-1} T_{|t|-1-j} x^j\). Tada su koeficijenti uz \(x^k\) za \(|t| - 1 \leq k \leq |s| - 1\) jednaki:
\[\sum_{j=0}^{|t|-1}S_{k-j}T_{|t|-1-j} = \sum_{j=0}^{|t|-1} S_{k-|t|+1+j}T_j\]
Primetimo da su ovo upravo zbirovi koji su nama potrebni: zbir za dati pomeraj \(i\) je koeficijent uz \(x^k\), za \(k = |t| - 1 + i\). Dakle, potrebno je samo formirati polinome \(P\) i \(Q\) na opisani način, pomnožiti ih (što možemo efikasno uraditi korišćenjem brze Furijeove transformacije) i pročitati koeficijente uz odgovarajuće stepene. Složenost ovog pristupa je \(O(|s|\log|s|)\).
string s, t;
cin >> s >> t;
// najmanji stepen dvojke veći od dužine prve niske
int n = pow2(s.size());
// koeficijenti prvog polinoma
ComplexVector S(n, 0);
for (int i = 0; i < s.size(); i++)
if (s[i] == '.')
S[i] = 1;
// koeficijenti drugog polinoma (smešteni u obratnom redosledu)
ComplexVector T(n, 0);
for (int i = 0; i < t.size(); i++)
if (t[t.size() - i - 1] == '.')
T[i] = 1;
// proizvod polinoma (korišćenjem fft i ifft)
ComplexVector st = mult(ss, tt);
// traženi brojevi su koeficijenti proizvoda
for (int i = 0; i <= s.length() - t.length(); i++)
cout << round(st[i + t.length() - 1].real()) << " ";#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef complex<double> Complex;
typedef vector<Complex> ComplexVector;
// brza Furijeova transformacija vektora a duzine n=2^k
// bool parametar inverse odredjuje da li je direktna ili inverzna
ComplexVector fft(const ComplexVector& a, bool inverse) {
// broj koeficijenata polinoma
int n = a.size();
// ako je stepen polinoma 0, vrednost u svakoj tacki jednaka
// je jedinom koeficijentu
if (n == 1)
return ComplexVector(1, a[0]);
// izdvajamo koeficijente na parnim i na neparnim pozicijama
ComplexVector Peven(n / 2), Podd(n / 2);
for (int i = 0; i < n / 2; i++) {
Peven[i] = a[2 * i];
Podd[i] = a[2 * i + 1];
}
// rekurzivno izracunavamo Furijeove transformacije tih polinoma
ComplexVector fftEven = fft(Peven, inverse),
fftOdd = fft(Podd, inverse);
// objedinjujemo rezultat
ComplexVector result(n);
for (int k = 0; k < n / 2; k++) {
// odredjujemo primitivni n-ti koren iz jedinice
double coeff = inverse ? -1.0 : 1.0;
Complex w = exp((coeff * 2 * k * M_PI / n) * 1i);
// racunamo vrednost polinoma u toj tacki
result[k] = fftEven[k] + w * fftOdd[k];
result[k + n/2] = fftEven[k] - w * fftOdd[k];
}
// vracamo konacan rezultat
return result;
}
// funkcija vrsi direktnu Furijeovu transformaciju polinoma ciji su
// koeficijenti odredjeni nizom a duzine 2^k
ComplexVector fft(const ComplexVector& a) {
return fft(a, false);
}
// funkcija vrsi inverznu Furijeovu transformaciju polinoma ciji su
// koeficijenti odredjeni nizom a duzine 2^k
ComplexVector ifft(const ComplexVector& a) {
ComplexVector rez = fft(a, true);
// nakon izracunavanja vrednosti, potrebno je jos podeliti
// sve koeficijente duzinom vektora
int n = a.size();
for (int k = 0; k < n; k++)
rez[k] /= n;
return rez;
}
// najmanji stepen dvojke koji je veći ili jednak x
int pow2(int n) {
int p = 1;
while (p < n)
p *= 2;
return p;
}
// proizvod polinoma
ComplexVector mult(const ComplexVector& a, const ComplexVector& b) {
int n = a.size();
ComplexVector fa = fft(a), fb = fft(b);
ComplexVector fc(n);
for (int i = 0; i < n; i++)
fc[i] = fa[i] * fb[i];
return ifft(fc);
}
int main() {
string s, t;
cin >> s >> t;
// najmanji stepen dvojke veći od dužine prve niske
int n = pow2(s.size());
// koeficijenti prvog polinoma
ComplexVector S(n, 0);
for (int i = 0; i < s.size(); i++)
if (s[i] == '.')
S[i] = 1;
// koeficijenti drugog polinoma (smešteni u obratnom redosledu)
ComplexVector T(n, 0);
for (int i = 0; i < t.size(); i++)
if (t[t.size() - i - 1] == '.')
T[i] = 1;
// proizvod polinoma (korišćenjem fft i ifft)
ComplexVector st = mult(ss, tt);
// traženi brojevi su koeficijenti proizvoda
for (int i = 0; i <= s.length() - t.length(); i++)
cout << round(st[i + t.length() - 1].real()) << " ";
cout << endl;
return 0;
}