Pagini recente » Cod sursa (job #417662) | Cod sursa (job #2155818) | Cod sursa (job #540451) | Cod sursa (job #697275) | Cod sursa (job #3235118)
#include <fstream>
#include <cstring>
using namespace std;
const int N = 2e6;
const int N_AFIS = 1000;
char a[N+2], b[N+2];
int pref[N+1], potriviri[N_AFIS];
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> (a + 1) >> (b + 1);///citim de la pozitia 1
///deocamdata prelucram doar sirul a
///construim vectorul pref cu semnificatia:
///pref[i] = j <=> j este lungimea maxima a unui prefix care e sufix al pref. de lung. i
///si j < i (a[1] = a[i-j+1] si a[2] = a[i-j+2] si ... a[j] = a[i])
int m = strlen(a + 1), lung_p;
pref[1] = lung_p = 0;///nu exista prefix de lungime < 1
for (int i = 2; i <= m; i++)
{
while (lung_p > 0 && a[i] != a[lung_p+1])///nu putem adauga a[i] la pref. curent
{
lung_p = pref[lung_p];
}
if (a[i] == a[lung_p+1])
{
lung_p++;
}
pref[i] = lung_p;
}
int n = strlen(b + 1), n_potriviri = 0;
lung_p = 0;
for (int j = 1; j <= n; j++)
{
///pe fiecare pozitie b gasim cel mai lung prefix din a care este sufix al
///prefixului de lungime j din b
while (lung_p > 0 && b[j] != a[lung_p+1])
{
lung_p = pref[lung_p];
}
if (b[j] == a[lung_p+1])
{
lung_p++;
}
if (lung_p == m)///intregul sir a este sufix al prefixului de lung j al lui b
{
n_potriviri++;
if (n_potriviri < N_AFIS)
{
///se termina pe poz j, deci incepe pe j - m + 1
potriviri[n_potriviri-1] = j - m + 1;
}
}
}
out << n_potriviri << "\n";
n_potriviri = min(n_potriviri, N_AFIS);
for (int i = 0; i < n_potriviri; i++)
{
out << potriviri[i] - 1 << " ";
}
out << "\n";
in.close();
out.close();
return 0;
}