Pagini recente » Cod sursa (job #2591420) | Cod sursa (job #1443902) | Cod sursa (job #578304) | Cod sursa (job #256067) | Cod sursa (job #2063563)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int put=1,l;
char a[2000005],sir[2000005];
vector <int> sol;
int fhash(char* start,char* finish)
{
int rez=*start;
put=1;
for(char* i=start+1;i!=finish;i++)
{
rez=(rez*256+(*i))%101;
put=(put*256)%101;
}
return rez%101;
}
void dummy(int poz)
{
for(int i=poz,j=0;i<poz+l;i++,j++)
{
if(sir[i]!=a[j])
return;
}
if(sol.size()<1000)
sol.push_back(poz);
}
void potrivire()
{
const int hashSirCautat=fhash(a,a+l);
int hashCurent=fhash(sir,sir+l);
for(int i=1;i<strlen(sir)-l+1;i++)
{
if(hashSirCautat==hashCurent)
dummy(i-1);
hashCurent=(((hashCurent-put*sir[i-1])%101+101)*256+sir[i+l-1])%101;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&a);
scanf("%s\n",&sir);
l=strlen(a);
potrivire();
printf("%d\n",sol.size());
for(int i=0;i<sol.size();i++)
printf("%d ",sol[i]);
return 0;
}