Pagini recente » Cod sursa (job #728562) | Cod sursa (job #3180251) | Cod sursa (job #1174981) | Cod sursa (job #2291222) | Cod sursa (job #3178816)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
long long pow1=1,pow2=1;
const long long MOD1=1e9+7;
const long long MOD2=4e9+7;
const long long ct=256;
void rolhash(long long &val, char c1, char c2, long long mod, long long pow)
{
val=((mod+val-pow*c1%mod)*ct+c2)%mod;
}
int poz[1001];
char pattern[2000001],txt[2000001];
int main()
{
cin>>pattern>>txt;
int n=strlen(pattern),m=strlen(txt),i;
long long hashp1=0,hashp2=0;
for(i=0;i<n-1;i++)
{
pow1=pow1*ct%MOD1;
pow2=pow2*ct%MOD2;
hashp1=(hashp1*ct+pattern[i])%MOD1;
hashp2=(hashp2*ct+pattern[i])%MOD2;
}
hashp1=(hashp1*ct+pattern[i])%MOD1;
hashp2=(hashp2*ct+pattern[i])%MOD2;
long long hash1=0,hash2=0;
int rez=0;
for(i=0;i<n&&i<m;i++)
{
hash1=(hash1*ct+txt[i])%MOD1;
hash2=(hash2*ct+txt[i])%MOD2;
}
i--;
while(i<m)
{
if(hash1==hashp1&&hash2==hashp2)
{
rez++;
poz[rez]=i-n+1;
}
i++;
hash1=((MOD1+hash1-pow1*txt[i-n]%MOD1)*ct+txt[i])%MOD1;
hash2=((MOD2+hash2-pow2*txt[i-n]%MOD2)*ct+txt[i])%MOD2;
}
cout<<rez<<'\n';
rez=min(rez,1000);
for(i=1;i<=rez;i++)
cout<<poz[i]<<" ";
return 0;
}