Pagini recente » Cod sursa (job #3182543) | Cod sursa (job #2451142) | Cod sursa (job #3243885) | Cod sursa (job #1352947) | Cod sursa (job #2451857)
#include <fstream>
#include <iostream>
#include <string.h>
using namespace std;
ifstream fin{"strmatch.in"};
ofstream fout{"strmatch.out"};
size_t sol[1001];
size_t k{0};
char A[2000002];
char B[2000002];
size_t prefix[2000002];
int main()
{
ios_base::sync_with_stdio(false);
fin.getline(A, 2000002, '\n');
fin.getline(B, 2000002, '\n');
size_t len_a = strlen(A);
size_t len_b = strlen(B);
for(size_t j = 0, i = 1; i < len_a;)
{
if(*(A + i) == *(A + j))
{
prefix[i] = j + 1;
++i;
++j;
}
else if(j != 0) j = prefix[j - 1];
else prefix[i++] = 0;
}
for(size_t j = 0, i = 0; i < len_b;)
{
if(A[j] == B[i])
{
++i;
++j;
} else if(j != 0) j = prefix[j - 1];
else ++i;
if(j == len_a) sol[++k] = i - j;
if(k == 1000) break;
}
fout << k << "\n";
for(size_t i = 1; i <= k; ++i) fout << sol[i] << " ";
}