Pagini recente » Cod sursa (job #1141656) | Cod sursa (job #2632431) | Cod sursa (job #1452648) | Cod sursa (job #119966) | Cod sursa (job #1123676)
#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(b);
scanf("\n");
gets(a);
scanf("\n");
n = strlen(a);
m = strlen(b);
}
void formareT()
{
int i, j;
T[0] = -1;
i = 1;
j = 0;
while (i < n)
{
if (a[i] == 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, k;
i = j = 0;
k = 0;
while (i + j < n)
{
if (a[i+j] == b[j])
{
j++;
k++;
if (k == m)
{
solutii.push_back(i);
j = k = 0;
i++;
}
}
else
{
k = 0;
i = i + j - T[j];
j = 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;
}