Pagini recente » Cod sursa (job #828367) | Cod sursa (job #2238929) | Cod sursa (job #1998860) | Cod sursa (job #559741) | Cod sursa (job #1125551)
#include <cstdio>
#include <cstring>
#include <vector>
#define lmax 2000000+5
using namespace std;
char mic[lmax], mare[lmax];
int nMic, nMare;
int cheie[lmax];
vector<int> solutii;
void citire()
{
gets(mic+1);
scanf("\n");
gets(mare+1);
scanf("\n");
nMic = strlen(mic+1);
nMare = strlen(mare+1);
}
void formareCheie()
{
int i, x;
for (i = 2, x = 0; i <= nMic; i++)
{
while (x && mic[x+1] != mic[i])
x = cheie[x];
if (mic[x+1] == mic[i])
x++;
cheie[i] = x;
}
}
void kmp()
{
int i, x;
for (i = 1, x = 0; i <= nMare; i++)
{
while (x && mic[x+1] != mare[i])
x = cheie[x];
if (mic[x+1] == mare[i])
x++;
if (x == nMic)
{
x = cheie[x];
solutii.push_back(i-nMic);
}
}
}
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();
formareCheie();
kmp();
afisare();
return 0;
}