Pagini recente » Cod sursa (job #520579) | Cod sursa (job #1875338) | Cod sursa (job #311365) | Cod sursa (job #2496696) | Cod sursa (job #2910663)
#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;
}