Pagini recente » Cod sursa (job #2357499) | Cod sursa (job #171998) | Cod sursa (job #3120566) | Cod sursa (job #1104259) | Cod sursa (job #1252777)
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m, i, k, t, pi[2000005], d[2000005];
char a[2000005], b[2000005];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a+1);
gets(b+1);
n=strlen(a+1);
m=strlen(b+1);
k=0;
pi[1]=0;
for(i=2;i<=n;i++)
{
while(k>0&&a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;
}
k=0;
for(i=1;i<=m;i++)
{
while(k>0&&a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
k++;
d[i]=k;
if(k==n) t++;
}
printf("%d\n", t);
k=0;
for(i=1;i<=m;i++)
if(d[i]==n)
{
k++;
printf("%d ", i-n);
if(k==1000) break;
}
return 0;
}