Pagini recente » Cod sursa (job #2583973) | Cod sursa (job #1700345) | Cod sursa (job #279078) | Cod sursa (job #2874643) | Cod sursa (job #1517081)
#include <iostream>
#include<cstdio>
#include<string.h>
#define n1 100007
#define n2 100021
using namespace std;
char s1[2000001], s2[2000001];
int poz[1100];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out","w", stdout);
int nr1=0, nr2=0, k1, k2, a1=0, a2=0, i, k=0, put1=1, put2=1;
gets(s2);
k2=strlen(s2);
gets(s1);
k1=strlen(s1);
if(k2>k1)
printf("0\n");
else{
for(i=0;i<k2;i++)
{
nr1=((nr1*123)%n1+s2[i])%n1;
nr2=((nr2*123)%n2+s2[i])%n2;
if(i!=0){
put1=(put1*123)%n1;
put2=(put2*123)%n2;
}
}
for(i=0;i<k2;i++)
{
a1=((a1*123)%n1+s1[i])%n1;
a2=((a2*123)%n2+s1[i])%n2;
}
if(a1==nr1&&a2==nr2)
poz[++k]=0;
for(i=k2;i<k1;i++)
{
//a1=(nr1-(put1*s1[i-k2])%n1+n1)%n1;
a1=a1-(put1*s1[i-k2])%n1;
if(a1<0)
a1+=n1;
a1%=n1;
//a2=(a2-(put2*s1[i-k2])%n2+n2)%n2;
a2=a2-(put2*s1[i-k2])%n2;
if(a2<0)
a2+=n2;
a1=((a1*123)%n1+s1[i])%n1;
a2=((a2*123)%n2+s1[i])%n2;
if(a1==nr1&&a2==nr2){
if(k<1000)
poz[++k]=i-k2+1;
}
}
printf("%d\n", min(k, 1000));
for(i=1;i<=k;i++)
{
printf("%d ", poz[i]);
}
}
return 0;
}