Pagini recente » Cod sursa (job #2895337) | Cod sursa (job #1548708) | Cod sursa (job #2738154) | Cod sursa (job #1883437) | Cod sursa (job #154761)
Cod sursa(job #154761)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define NMAX 2000002
char A[NMAX],B[NMAX];
long int pi[NMAX];
long int n,k,m,i;
int cnt;
long int sol[1001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",A);
scanf("%s",B);
n=strlen(A);
m=strlen(B);
k=0;
pi[1]=0;
for (i=2;i<=n;i++)
{
for (;k&&(A[i-1]!=A[k]);)
k=pi[k];
if (A[i-1]==A[k]) k++;
pi[i]=k;
}
k=0;
for (i=1;i<=m;i++)
{
for (;k&&(B[i-1]!=A[k]);) k=pi[k];
if (B[i-1]==A[k]) k++;
if (k==n) {
++cnt;
if (cnt<=1000) sol[cnt]=i-n;
}
}
printf("%ld\n",cnt);
for (i=1;i<=min(cnt,1000);i++)
printf("%ld ",sol[i]);
return 0;
}