Pagini recente » Monitorul de evaluare | Cod sursa (job #999337) | Cod sursa (job #1784060) | Cod sursa (job #892369) | Cod sursa (job #806102)
Cod sursa(job #806102)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
FILE * iFile;
FILE * oFile;
vector<int> sol;
char A[2000010], B[2000010];
int p[2000010], la, lb, n;
void prefix()
{
int q;
p[1] = 0;
q = 0;
for(int i=2;i<=la;i++)
{
while(q > 0 && A[q+1] != B[i])
q = p[q];
if(A[q+1] == B[i])
q++;
p[i] = q;
}
}
void match()
{
int q;
q=0;
for(int i=1;i<=lb;i++)
{
while(q>0&&A[q+1] != B[i])
q = p[q];
if(A[q+1] == B[i])
q++;
if(q == la)
{
n++;
if(n <= 1000)
sol.push_back(i-q);
q=p[q];
}
}
}
void read()
{
fscanf(iFile, "%s", A+1);
fscanf(iFile, "%s", B+1);
}
void write()
{
fprintf(oFile, "%d\n", n);
for(int i=0;i<sol.size();i++)
fprintf(oFile, "%d ", sol[i]);
}
int main()
{
iFile = fopen("strmatch.in", "r");
oFile = fopen("strmatch.out", "w");
read();
la=strlen(A+1);
lb=strlen(B+1);
prefix();
match();
write();
fclose(iFile);
fclose(oFile);
return 0;
}