Pagini recente » Cod sursa (job #811943) | Cod sursa (job #460920) | Cod sursa (job #2810554) | Cod sursa (job #2163791) | Cod sursa (job #2078782)
/// 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;
}
if(A < 1000 && B < 1000)
{
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;
}
}
}
else
{
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;
else if(j_curent != 0) j_curent = v[j_curent - 1];
else i_curent++;
if(j_curent == 1000)
{
sol[++foo] = i_curent - 1000;
j_curent = 0;
--i_curent;
}
}
}
g << foo << '\n';
for(int i = 1; i <= foo; ++i)
g << sol[i] << " ";
return 0;
}