Pagini recente » Cod sursa (job #1487797) | Autentificare | Cod sursa (job #3000035) | Cod sursa (job #1954609) | Cod sursa (job #2063343)
#include <iostream>
#include <cstdio>
#include <cstring>
#define NMAX 2000005
using namespace std;
char s[NMAX], p[NMAX];
int vPS[NMAX], sol[1005];
void prefixSufix()
{
int l = strlen(p);
int i=1, j=0;
vPS[0] = 0;
while(i < l)
{
while(j > 0 && p[j] != p[i])
j = vPS[j-1];
if(p[j] == p[i])
j++;
vPS[i] = j;
i++;
}
}
void gasireSubsir()
{
int l = strlen(s), lp = strlen(p), j = 0;
for(int i=0; i<l; ++i)
{
while(j > 0 && s[i] != p[j])
j = vPS[j-1];
if(s[i] == p[j])
j++;
if(j == lp)
{
sol[++sol[0]] = i-lp+1;
if(sol[0] > 1000)
return;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", &p, &s);
prefixSufix();
gasireSubsir();
printf("%d\n", sol[0]);
for(int i=1; i<=sol[0]; ++i)
printf("%d ", sol[i]);
return 0;
}