Pagini recente » Autentificare | Cod sursa (job #994047) | Cod sursa (job #171264) | Cod sursa (job #2817844) | Cod sursa (job #2078743)
/// KMP COMPARARE DE SIRURI
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <utility>
#include <algorithm>
#define NMax 2000001
///#define f cin
///#define g cout
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int A, B, v[NMax], ans, sol[NMax], foo;
char a[NMax], b[NMax];
int main()
{
f.getline(a, NMax);
f.getline(b, NMax);
A = strlen(a); /// pattern-ul care trebuie verificat daca exista in text
B = strlen(b); /// textul initial
for(int i = 1; i < A;) /// construiesc vectorul temporar pentru pattern-ul care trebuie gasit
if(a[i] == a[ans]) /// daca sunt egale (gasesc un prefix egal cu un sufix) atunci in vectorul temporar se adauga orice pozitie e ans + 1
{
v[i] = ans + 1;
++ans;
++i; /// si continuam sa verificam
}
else if(ans != 0) ans = v[ans - 1]; /// daca nu sunt egale te duci la valoarea de la caracterul dinainte si ans o sa devina valoarea aia ceea ce inseamna ca de acolo trebuie sa inceapa verificarea din nou
else /// daca nu sunt egale pur si simplu setam valoarea cu 0 si continuam sa verificam
{
v[i] = 0;
++i;
}
int i_curent = 0, j_curent = 0;
while(i_curent < B && j_curent < A)
{
if(b[i_curent] == a[j_curent]) ++i_curent, ++j_curent; /// daca sunt egale... continuam sa verificam
else if(j_curent != 0) j_curent = v[j_curent - 1]; /// daca nu sunt egale si contorul pattern-ului e diferit de 0 atunci ii dam valoarea caracterului de dinainte
else i_curent++; /// daca nu sunt egale continuam...
if(j_curent == A) /// daca contorul e egal cu lungimea pattern-ului atunci adaugam solutie
{
sol[++foo] = i_curent - A; /// adugam pozitia de inceput unde e gasita aparitia si numaram solutia
j_curent = 0; /// resetam contorul
--i_curent;
}
}
g << foo << '\n';
for(int i = 1; i <= foo; ++i)
g << sol[i] << " ";
return 0;
}