Pagini recente » Cod sursa (job #1042080) | Cod sursa (job #2971475) | Cod sursa (job #152933) | Cod sursa (job #1862479) | Cod sursa (job #841018)
Cod sursa(job #841018)
#include<cstdio>
#include<cstring>
#define LMAX 2000000+10
using namespace std;
char A[LMAX],B[LMAX];
int LA,LB,pi[LMAX],top,st[1010];
void prefix() //Calculam prefixele = sufixele de lungime maxima pana la pozitia i a sirului A (si diferite de sirul in sine)
{
int q=0,i;
for(i=2;i<=LA;i++)
{
for(;q;)
{
if(A[q+1]==A[i]) break;
else q=pi[q];
}
if(A[q+1]==A[i]) q++;
pi[i]=q;
}
}
void potrivire() //Potrivim prefixele lui A cu sirul B pana gasim A inclus in B => adaugam in stiva de solutii
{
int i,q=0;
for(i=1;i<=LB;i++)
{
for(;q;)
{
if(B[i]==A[q+1]) break;
else q=pi[q];
}
if(B[i]==A[q+1]) q++;
if(q==LA)
{
top++;
if(top<=1000) st[top]=i-q;
q=pi[q];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",A+1);
scanf("%s",B+1);
LA=strlen(A+1);
LB=strlen(B+1);
prefix();
potrivire();
printf("%d\n",top); top=top<1000?top:1000;
for(int i=1;i<=top;i++) printf("%d ",st[i]);
return 0;
}