Pagini recente » Cod sursa (job #2739997) | Cod sursa (job #3254484) | Cod sursa (job #1010070) | Cod sursa (job #1964445) | Cod sursa (job #1123733)
#include <cstdio>
#include <cstring>
#include <vector>
#define lmax 2000000+5
using namespace std;
char a[lmax], b[lmax];
int n, m;
int T[lmax];
vector<int> solutii;
void citire()
{
gets(a);
scanf("\n");
gets(b);
scanf("\n");
n = strlen(a);
m = strlen(b);
}
void formareT()
{
int i, j;
T[0] = -1;
i = 2;
j = 0;
while (i < n)
{
if (a[i-1] == a[j])
{
j += 1;
T[i] = j;
i += 1;
}
else if (j > 0)
j = T[j];
else
{
T[i] = 0;
i += 1;
}
}
}
void gasire()
{
int i, j;
i = j = 0;
while (i + j < m)
{
if (b[i+j] == a[i])
{
i++;
if (i == n)
{
solutii.push_back(j);
i = 0;
j++;
}
}
else
{
j = j + i - T[i];
if (T[i] >= 0)
i = T[i];
else
i = 0;
}
}
}
void afisare()
{
int i;
printf("%d\n", solutii.size());
for (i = 0; i < solutii.size() && i < 1000; i++)
printf("%d ", solutii[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
formareT();
gasire();
afisare();
return 0;
}