Pagini recente » Cod sursa (job #2319661) | Cod sursa (job #3191835) | Cod sursa (job #2476628) | Cod sursa (job #2713993) | Cod sursa (job #2451860)
#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 ) {
k++;
if(k <= 1000) sol[k] = i - j;
}
}
fout << k << "\n";
if(k > 1000) k = 1000;
for(size_t i = 1; i <= k; ++i) fout << sol[i] << " ";
}