Pagini recente » Cod sursa (job #3282897) | Cod sursa (job #2252922) | Cod sursa (job #418272) | Cod sursa (job #999109) | Cod sursa (job #629486)
Cod sursa(job #629486)
#include <cstdio>
#include <cstring>
#define p 1000000000
#define baza 52
#define lmax 2000005
using namespace std;
long long nra, nrb, k, i, la, lb, rez, blan, x, vrez[1005];
bool ok;
char a[lmax], b[lmax];
void verificare()
{
ok=1;
for (k=0;(k<lb&&ok);k++)
ok=(b[k]==a[i+k]);
rez+=ok;
if ((rez<=1000) &&(ok))
vrez[rez]=i;
}
long long put(long k)
{
long long pj;
if (k==0)
return 1;
pj=put(k/2);
if (k%2==0)
return (pj*pj)%p;
return (((pj*pj)%p)*baza)%p;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(b); gets(a);
la=strlen(a); lb=strlen(b);
blan=put(lb-1);
for (i=0;i<lb;i++)
{
x=a[i]-'A'+26;
if ((a[i]>='a')&&(a[i]<='z'))
x=a[i]-'a';
nra=(nra*baza+x)%p;
x=b[i]-'A'+26;
if ((b[i]>='a')&&(b[i]<='z'))
x=b[i]-'a';
nrb=(nrb*baza+x)%p;
}
i=0;
if (nra==nrb)
verificare();
for (i=1;i<=la-lb;i++)
{
x=a[i-1]-'A'+26;
if ((a[i-1]>='a')&&(a[i-1]<='z'))
x=a[i-1]-'a';
nra=(nra-blan*x)%p;
nra=(nra*baza)%p;
x=a[i+lb-1]-'A'+26;
if ((a[i+lb-1]>='a')&&(a[i+lb-1]<='z'))
x=a[i+lb-1]-'a';
nra+=x;
nra=(nra+p)%p;
if (nra==nrb)
verificare();
}
printf("%ld\n",rez);
for (i=1;i<=rez;i++)
printf("%ld ",vrez[i]);
return 0;
}