Pagini recente » Cod sursa (job #1455008) | Cod sursa (job #850405) | Cod sursa (job #1987273) | Cod sursa (job #77977) | Cod sursa (job #378191)
Cod sursa(job #378191)
#include <cstdio>
#include <cstring>
#define NMAX 2000002
#define MMAX 2000001
int URM[MMAX];
char T[NMAX],P[MMAX];
int SOL[NMAX],NR=0;
int N,M;
void urmatorul(char *P)
{
int k=-1;
URM[0]=0;
for(int i=1;i<M;i++)
{
while(k>0 && P[k+1]!=P[i])
k=URM[k];
if(P[k+1]==P[i])
k++;
URM[i]=k;
}
}
int main()
{
int x=-1;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(P);
gets(T);
M=strlen(P);
N=strlen(T);
urmatorul(P);
for(int i=0;i<N;i++)
{
while(x>0 && P[x+1]!=T[i])
x=URM[x];
if(P[x+1]==T[i])
x++;
if(x==M-1)
{
SOL[++NR]=i-M+1;
x=URM[x];
}
}
printf("%d\n",NR);
for(int i=1;i<=NR;i++)
printf("%d ",SOL[i]);
return 0;
}