Pagini recente » Cod sursa (job #54357) | Cod sursa (job #23229) | Cod sursa (job #2731621) | Cod sursa (job #2783213) | Cod sursa (job #978899)
Cod sursa(job #978899)
#include<cstdio>
#include<cstring>
#define B1 101
#define B2 109
#define MOD1 10013
#define MOD2 666013
using namespace std;
char s[2000010];
int v[2000010];
int VAL1,VAL2,P1,P2,NR1,NR2,i,n,nr,m;
//verificarea valorilor
inline bool verif ()
{
if ((VAL1==NR1) && (VAL2==NR2)) return true;
else return false;
}
//calcularea puterilor
inline void GenPutere(int n, int &nr1,int &nr2)
{
int a=B1,b=B2,p=n,i;
for (i = 0; (1<<i) <= p; i++)
{
if ( ((1<<i) & p) > 0)
{
nr1= (nr1 * a) % MOD1;
nr2= (nr2 * b) % MOD2;
}
a=(a *a) %MOD1;
b=(b*b) %MOD2;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s);
nr=0;
n=strlen(s);
//precalculare valori - primul sir
for (i=0;i<n;i++)
{
P1=1;
P2=1;
GenPutere(n-i-1,P1,P2);
VAL1+=((s[i])*P1)%MOD1;
VAL1%=MOD1;
VAL2+=((s[i])*P2)%MOD2;
VAL2%=MOD2;
}
gets(s);
m=strlen(s);
//precalculare valori - al doilea sir
for (i=0;i<n;i++)
{
P1=1;
P2=1;
GenPutere(n-i-1,P1,P2);
NR1+=((s[i])*P1)%MOD1;
NR1%=MOD1;
NR2+=((s[i])*P2)%MOD2;
NR2%=MOD2;
}
if (verif())
{
nr++;
v[nr]=0;
}
//calculare valori - al doilea sir -
P1=1;
P2=1;
GenPutere(n-1,P1,P2);
for (i=n;i<m;i++)
{
NR1=(((NR1-s[i-n]*P1) % MOD1 + MOD1) * B1 + s[i]) % MOD1;
NR2=(((NR2-s[i-n]*P2) % MOD2 + MOD2) * B2 + s[i]) % MOD2;
if (verif())
{
nr++;
v[nr]=i-n+1;
}
}
printf("%d\n",nr);
for (i=1;i<=nr;i++)
printf("%d ",v[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}