Pagini recente » Statistici ArinaTeen (ArinaTeen) | Cod sursa (job #1307652) | Cod sursa (job #2521349) | Cod sursa (job #158557) | Cod sursa (job #723482)
Cod sursa(job #723482)
#include <fstream>
#include <string.h>
using namespace std;
char A[2000005];
char B[2000005];
char prefix[2000005];
long res[1024];
int main(void)
{
fstream fin("strmatch.in",ios::in);
fstream fout("strmatch.out",ios::out);
fin >> (B + 1) >> (A + 1);
long la,lb,i,j,c;
la = strlen(A + 1);
lb = strlen(B + 1);
c = 0;
j = 0;
prefix[1] = 0;
for (i = 2;i <= lb;i += 1)
{
while ((j > 0) && (B[j + 1] != B[i]))
{
j = prefix[j];
}
if (B[j + 1] == B[i])
{
j += 1;
}
prefix[i] = j;
}
j = 0;
for (i = 1;i <= la;i += 1)
{
while ((j > 0) && (B[j + 1] != A[i]))
{
j = prefix[j];
}
if (B[j + 1] == A[i])
{
j += 1;
}
if (j == lb)
{
j = prefix[lb];
if (c < 1000)
{
res[c] = i - lb;
}
c += 1;
}
}
fout << c << "\n";
if (c > 1000)
{
c = 1000;
}
for (i = 0;i < c;i += 1)
{
fout << res[i] << " ";
}
fin.close();
fout.close();
return 0;
}