Pagini recente » Cod sursa (job #1017651) | Cod sursa (job #1259356) | Cod sursa (job #2632465) | Cod sursa (job #2784219) | Cod sursa (job #2191866)
#include <iostream>
#include <fstream>
#include <cstring>
#define q 97
#define d 2
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000001],p[2000001];
int poz[1001],nrElemente;
long long int h,pow,val;
long long int putere(long long int a,long long int b)
{
if(b==0) return 1;
else if(b==1) return a;
else if(b%2==0) return putere(a,b/2) * putere(a,b/2);
else return a * putere(a,b/2) * putere(a,b/2);
}
void calculHash(long long int x)
{
if(h)
{
//h-= ((int) (s[x-1]) * val) % q;
h= (h - ( (int) (s[x-1]) * val ) ) * d + (int) (s[x+strlen(p)-1]) ;
//return h;
}
}
int main()
{
fin.getline(p,2000001);
fin.getline(s,2000001);
if(strlen(p)>strlen(s))
{
fout<<0;
return 0;
}
pow=1;
long long int hashp=0;
for(int i=strlen(p)-1;i>=0;--i)
{
h= h + ((int) (s[i]) * pow);
hashp= hashp + ((int) (p[i]) * pow);
pow=pow * d;
}
int contor=0;
val=putere(d,strlen(p)-1);
for(int i=0;i<=strlen(s)-strlen(p);++i)
{
if(h==hashp)
{
bool gasit=true;
for(int j=0;j<strlen(p);++j)
{
if(p[j]!=s[i+j])
{
gasit=false;
break;
}
}
if(gasit)
{
contor++;
poz[nrElemente++]=i;
}
}
calculHash(i+1);
}
fout<<contor<<"\n";
for(int i=0;i<nrElemente;++i) fout<<poz[i]<<" ";
return 0;
}