Pagini recente » Cod sursa (job #2441890) | Cod sursa (job #2592011) | Cod sursa (job #2569075) | Cod sursa (job #1220061) | Cod sursa (job #1969488)
#include <bits/stdc++.h>
#define Nmax 2000005
#define M1 10007
#define M2 666013
#define P 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[Nmax];
char v[Nmax];
char x[Nmax];
int poz[1001];
int n,m,P1=1,P2=1;
int main()
{f>>v>>s;
int h1=0,h2=0,hash1=0,hash2=0;
for(int i=0;v[i];i++)
{
h1=(h1*P+v[i])%M1;
h2=(h2*P+v[i])%M2;
hash1=(hash1*P+s[i])%M1;
hash2=(hash2*P+s[i])%M2;
if(i!=0)
P1=(P1*P)%M1,
P2=(P2*P)%M2;
}
n=strlen(v);
m=strlen(s);
if(m<n)
{
g<<0;
return 0;
}
int nr=0;
if(h1==hash1 and h2==hash2)
poz[++nr]=0;
for(int i=n;s[i];i++)
{
hash1=((hash1-(s[i-n]*P1)%M1+M1)*P+s[i])%M1;
hash2=((hash2-(s[i-n]*P2)%M2+M2)*P+s[i])%M2;
if(hash1==h1 and h2==hash2)
{
nr++;
if(nr<1001)
poz[nr]=i-n+1;
}
}
g<<nr<<'\n';
nr=min(nr,1000);
for(int i=1;i<=nr;i++)
g<<poz[i]<<' ';
return 0;
}