Pagini recente » Cod sursa (job #1133556) | Cod sursa (job #1775779) | Cod sursa (job #2056369) | Cod sursa (job #1346182) | Cod sursa (job #1889259)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int nmx = 2000005;
char a[nmx],b[nmx];
int la,lb;
int p[nmx],dp[nmx];
int total[1002];
void citire()
{
scanf("%s", a);
la = strlen(a);
scanf("%s", b);
lb = strlen(b);
}
void prefix()
{
int i = 1, j = 0;
while(i < la)
{
if(a[i] == a[j])
{
p[i] = j + 1;
++ i;
++ j;
}
else if(j)
j = p[j-1];
else
++ i;
}
}
void kmp()
{
int i = 0, j = 0;
while(i < lb)
{
if(b[i] == a[j])
{
dp[i+1] = j + 1;
++ i;
++ j;
if(j == la)
{
++ total[0];
if(total[0] <= 1000)
total[total[0]] = i - la;
}
}
else if(j)
j = p[j-1];
else
++ i;
}
}
void afish()
{
int lim = min(total[0],1000);
printf("%d\n", total[0]);
for(int i = 1; i <= lim; ++i)
printf("%d ", total[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
prefix();
kmp();
afish();
return 0;
}