Pagini recente » Cod sursa (job #1383227) | Cod sursa (job #3146833) | Cod sursa (job #2935990) | Cod sursa (job #726284) | Cod sursa (job #2232395)
#include <stdio.h>
#include <string.h>
using namespace std;
char sir[2000005], pat[2000005];
int n, m, nrpos, pos[2000005];//n=lung sir, m=lung pat
int h1pat, h2pat, p1max=1, p2max=1, h1, h2, mod1=100007 , mod2=100021., p=73;
//h1pat=( pat[0]*p^(m-1)+ pat[1]*p^(m-2)+ ...+pat[m-1]*p^0)%mod1
//h2pat=( pat[0]*p^(m-1)+ pat[1]*p^(m-2)+ ...+pat[m-1]*p^0)%mod1
//p1max= p^(m-1)%mod1
//p2max= p^(m-1)%mod2
void citire()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s%s", pat, sir);
m=strlen(pat); n=strlen(sir);
for(int i=0; i<m; i++)
{
h1pat=(h1pat*p+pat[i])%mod1;
h2pat=(h2pat*p+pat[i])%mod2;
if(i>0)
{
p1max*=p; p1max%=mod1;
p2max*=p; p2max%=mod2;
}
}
if(n<m) return;
for(int i=0; i<m; i++)
{
h1=(h1*p+sir[i])%mod1;
h2=(h2*p+sir[i])%mod2;
}
if((h1==h1pat)&&(h2==h2pat))
{
nrpos++; pos[nrpos]=0;
}
for(int i=m; i<n; i++)
{
h1=(((h1-sir[i-m]*p1max)%mod1 +mod1) *p + sir[i])%mod1;
h2=(((h2-sir[i-m]*p2max)%mod2 +mod2)*p + sir[i])%mod2;
if((h1==h1pat)&&(h2==h2pat))
{
nrpos++; pos[nrpos]=i-m+1;
}
}
}
void afis()
{
printf("%d\n", nrpos);
for(int i=1; (i<=nrpos)&&(i<=1000); i++)
printf("%d ", pos[i]);
printf("\n");
}
int main()
{
citire();
afis();
return 0;
}