Pagini recente » Cod sursa (job #81294) | Cod sursa (job #942840) | Cod sursa (job #3190767) | Cod sursa (job #2915569) | Cod sursa (job #1517836)
#include<cstdio>
#include<cstring>
bool poz[2000001];
char s1[2000001],s2[2000001];
char get_hash(char ch)
{
if(ch>='A' && ch<='Z')
ch=ch-'A'+1;
else
if(ch>='a' && ch<='z')
ch=ch-'a'+27;
else
ch=ch-'0'+53;
return ch;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s ",s1,s2);
int n1=strlen(s1),n2=strlen(s2),H1=0,H2=0;
int put=1;
for(int i=n1-1;i>=0;i--)
{
s1[i]=get_hash(s1[i]);
H1=(H1+s1[i]*put)%100007;
if(i!=0)
{
put*=63;
put%=100007;
}
}
if(n1>n2)
{
printf("0\n");
return 0;
}
put=1;
for(int i=n1-1;i>=0;i--)
{
s2[i]=get_hash(s2[i]);
//H2=(H2*73+s2[i])%100007;
H2=(H2+s2[i]*put)%100007;
if(i!=0)
{
put*=63;
put%=100007;
}
}
int rasp=0;
if(H1==H2)
{
rasp++;
poz[0]=true;
}
for(int i=n1;i<n2;i++)
{
s2[i]=get_hash(s2[i]);
H2=((H2-(s2[i-n1]*put)%100007)*63+s2[i])%100007;
if(H2==H1)
{
rasp++;
poz[i-n1+1]=true;
}
}
printf("%d\n",rasp);
for(int i=0;i<=n2 && i<1000;i++)
{
if(poz[i])
printf("%d ",i);
}
fclose(stdin);
fclose(stdout);
return 0;
}