Pagini recente » Cod sursa (job #3278088) | Cod sursa (job #1056813) | Cod sursa (job #1270315) | Cod sursa (job #512138) | Cod sursa (job #2910658)
#include <fstream>
#include <cstring>
#define DIM 2000002
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[DIM], b[DIM];
int p[DIM];
int n = 0, sol[1001];
int main()
{
fin >> (a + 1) >> (b + 1);
int lenA = strlen(a + 1);
int lenB = strlen(b + 1);
int L = 0;
p[1] = 0;
for (int i = 2; i <= lenA; i++)
{
while (L != 0 && a[i] != a[L + 1])
L = p[L];
if (a[i] == a[L + 1])
L++;
p[i] = L;
}
L = 0;
for (int i = 1; i <= lenB; i++)
{
while (L != 0 && b[i] != a[L + 1])
L = p[L];
if (b[i] == a[L + 1])
L++;
if (L == lenA)
{
n++;
if (n <= 1000)
sol[n] = i - lenA;
L = p[L];
}
}
fout << n << '\n';
for (int i = 1; i <= min(n, 1000); i++)
fout << sol[i] << ' ';
return 0;
}