Pagini recente » Cod sursa (job #2500537) | Cod sursa (job #2890963) | Cod sursa (job #218699) | Cod sursa (job #554155) | Cod sursa (job #2194909)
#include <iostream>
#include <fstream>
#include <cstring>
#define q 101
#define d 256
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000001],p[2000001];
int poz[1001],nrElemente;
long long int hashs,pow;
long long int putere(long long int a,long long int b)
{
if(b==0) return 1;
else if(b==1) return a % q;
else if(b%2==0) return (putere(a,b/2) * putere(a,b/2)) % q;
else return (a * putere(a,b/2) * putere(a,b/2)) % q;
}
void calculHash(long long int poz)
{
hashs= ( (hashs-s[poz]*pow)*d + s[poz+strlen(p)] ) % q;
if(hashs<0) hashs+=q;
}
int main()
{
fin.getline(p,2000001);
fin.getline(s,2000001);
int lg_p=strlen(p);
int lg_s=strlen(s);
if(lg_p > lg_s)
{
fout<<0;
return 0;
}
long long int hashp=0;
for(int i=0;i<lg_p;++i)
{
hashs=(hashs*d+s[i])%q;
hashp=(hashp*d+p[i])%q;
}
pow=putere(d,lg_p-1);
/*pow=1;
for(int i=0;i<lg_p-1;++i)
{
pow=(pow*d)%q;
}*/
/*pow=1;
for(int i=lg_p-1;i>=0;--i)
{
hashs=( hashs + ((int) (s[i]) * pow) % q) % q;
hashp=( hashp + ((int) (p[i]) * pow) % q ) %q;
if(i>0) pow=(pow * d) % q;
}*/
for(int i=0;i<=lg_s-lg_p;++i)
{
if(hashs==hashp)
{
int j=0;
for(j=0;j<lg_p;++j)
{
if(p[j]!=s[i+j]) break;
}
if(j==lg_p)
{
if(nrElemente<1000) poz[nrElemente++]=i;
else nrElemente++;
}
}
calculHash(i);
}
fout<<nrElemente<<"\n";
if(nrElemente>1000) nrElemente=1000;
for(int i=0;i<nrElemente;++i) fout<<poz[i]<<" ";
return 0;
}