Pagini recente » Clasament dupa rating | Profil Andrei-27 | Statistici Bogoi Ionut (FMI_Bogoi_Ionut) | Monitorul de evaluare | Cod sursa (job #2005968)
#include <fstream>
#include <cstring>
using namespace std;
const int NMAX = 2000005;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char A[NMAX],B[NMAX];
int prefix[NMAX],poz[1005];
int main()
{
in.getline(A,NMAX);
in.getline(B,NMAX);
int LengthA = strlen(A),LengthB = strlen(B);
int i,j=0;
for (i = 1; i<LengthA;)
{
if (A[i] == A[j])
{
prefix[i]+=j+1;
j++;
i++;
}
else
{
if (j != 0)
j = prefix[j-1];
else
{
prefix[i] = 0;
i++;
}
}
}
j = 0;
int pz = 0,k=0;
for (i = 0; i<LengthB;)
{
if (B[i] == A[j])
{
i++;
j++;
}
else
{
if (j != 0)
j = prefix[j-1];
else
{
j = 0;
i++;
}
pz = i;
}
if (j == LengthA && k<=1000)
{
poz[k++] = pz;
j = 0;
i--;
pz = i;
}
}
out << k << "\n";
for (i = 0; i<k; i++)
out << poz[i] << " ";
}