Pagini recente » Cod sursa (job #2226670) | Cod sursa (job #1424844) | Cod sursa (job #2223737) | Cod sursa (job #212021) | Cod sursa (job #2217314)
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int DIM = 2000001;
char text[DIM * 2];
int P, lg;
int Z[DIM * 2], ap[1001], nrap;
//Z[k] reprezinta cea mai lunga secv care incepe la text[k] si este in acelasi timp prefix al lui text
void z_algorithm(char *text, int P, int lg)
{
//pt fiecare k calculam capetele L si R ale secventei a.i. aceasta sa respecte conditia de matching cu prefixul de aceeasi lungime si sa aiba R maxim
int L = 0, R = 0;
Z[0] = lg;
for(int k = 1; k < lg; k++)
{
if(k > R)
{
int i;
for(i = 0; i + k < lg && text[i] == text[i + k]; i++);
Z[k] = i;
if(Z[k])
{
L = k;
R = k + Z[k] - 1;
}
}
else if(k <= R)
{
int A = R - L + 1, B = R - k + 1, k2 = k - L;
if(Z[k2] < B) ///L si R raman aceleasi
Z[k] = Z[k2];
else
{
int i;
for(i = B; i + k < lg && text[i] == text[i + k]; i++);
Z[k] = i;
L = k;
R = k + Z[k] - 1;
}
}
if(k >= P && Z[k] >= P)
{
nrap++;
if(nrap <= 1000)
ap[nrap] = k - P;
}
}
}
int main()
{
in.getline(text, DIM);
P = in.gcount() - 1;
in.getline(text + P, DIM);
lg = P + in.gcount() - 1;
//am unit sirurile pattern + text
if(P * 2 > lg)
{
out << 0;
return 0;
}
z_algorithm(text, P, lg);
out << nrap << '\n';
for(int i = 1; i <= nrap && i <= 1000; i++)
out << ap[i] << ' ';
return 0;
}