Pagini recente » Cod sursa (job #1452885) | Cod sursa (job #1920945) | Cod sursa (job #1583419) | Cod sursa (job #248091) | Cod sursa (job #1081245)
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxN 2000005
char T[maxN],P[maxN];
int n,m,v[maxN];
unsigned long power(int d,int m)
{
int i;
unsigned long p=1;
for(i=1; i<m ;i++) p*=d;
return p;
}
int EQ(char *P,char *T,int k)
{
int i;
for(i=0; i<m ;i++)
if(P[i]!=T[k+i]) return 0;
return 1;
}
int str_match(char *T,char *P,int d,int q)
{
unsigned long h,p,t0;
int i,k,nr=0;
n=strlen(T); m=strlen(P);
h=power(d,m)%q;
p=0; t0=0;
for(i=0; i<m ;i++)
{
p=(d*p+P[i])%q;
t0=(d*t0+T[i])%q;
}
for(k=0; k<=n-m ;k++)
{
if(p==t0)
if(EQ(P,T,k)) v[nr++]=k;
t0=(t0+d*q-T[k]*h)%q;
t0=(t0*d+T[k+m])%q;
}
if(nr>0) return nr;
else return 0;
}
int main()
{
int i,nr_poz;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",P,T);
nr_poz=str_match(T,P,128,666013);
if(nr_poz>0)
{
printf("%d\n", nr_poz);
if(nr_poz>1000)
{
for(i=0; i<1000 ;i++)
printf("%d ",v[i]);
}
else
{
for(i=0; i<nr_poz ;i++)
printf("%d ",v[i]);
}
}
else printf("%d\n", nr_poz);
fclose(stdout);
return 0;
}