Pagini recente » Cod sursa (job #610477) | Cod sursa (job #2530561) | Cod sursa (job #2114886) | Cod sursa (job #1904888) | Cod sursa (job #1006332)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000002
using namespace std;
char a[N], b[N];
int pi[N], sol[1001];
void kmp()
{
int q=0, i;
for(i=2;a[i]!='\n'&&a[i]!='\0';i++)
{
while(q&&a[q+1]!=a[i]) q=pi[q];
if(a[q+1]==a[i]) q++;
pi[i]=q;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, q=0, soll=0, m;
a[0]='0';
gets(a+1);
m=strlen(a)-1;
gets(b+1);
kmp();
for(i=1;b[i]!='\n'&&b[i]!='\0';i++)
{
while(q&&a[q+1]!=b[i]) q=pi[q];
if(a[q+1]==b[i]) q++;
if(q==m)
{
soll++;
if(soll<=1000) sol[soll]=i-m;
}
}
printf("%d\n", soll);
for(i=1;i<=min(soll, 1000);i++) printf("%d ", sol[i]);
}