Pagini recente » Cod sursa (job #1262094) | Cod sursa (job #558635) | Cod sursa (job #2866817) | Cod sursa (job #1463077) | Cod sursa (job #348317)
Cod sursa(job #348317)
#include <stdio.h>
#define P 1<<21
#define Q 1<<10
char M[P],N[P];
int m,n,pi[P],nr,sol[P];
inline int lit(char x)
{
return (x>='A' && x<='Z') || (x>='a' && x<='z') ||
(x>='0' && x<='9');
}
void calc_prefix()//cel mai lung prefix care e si sufix pt sirul N
{
int k=0,i;
for (i=2; i<=n; i++)
{
while (k>0 && N[k+1]!=N[i])k=pi[k];
/*"trec la configuratiile anterioare de prefixe
care sunt si sufixe" si gasesc o potrivire*/
if (N[k+1]==N[i])k++;//"potrivire cu configuratia anterioara"
pi[i]=k;
}
}
void kmp()
{
int i,q=0;
for (i=1; i<=m; i++)
{
while (q>0 && N[q+1] != M[i]) q=pi[q];//se incearca potriviri
if ( N[q+1] == M[i]) q++;//potrivire pt primele q pozitii
if ( q == n)//potrivire perfecta
{
nr++;
if (nr<=1000)sol[nr]=i-n;
}
}
}
inline int min(int a,int b)
{
if (a<b)
return a;
return b;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(N+1,P,stdin);
while (lit(N[n+1])) n++;
fgets(M+1,P,stdin);
while (lit(M[m+1])) m++;
calc_prefix();
kmp();
printf("%d\n",nr);
int i,t=min(nr,1000);
for (int i=1; i<=t; i++)
printf("%d ",sol[i]);
return 0;
}