Pagini recente » Cod sursa (job #2811841) | Cod sursa (job #1569049) | Cod sursa (job #2270714) | Cod sursa (job #2009692) | Cod sursa (job #2186705)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char a[2000005],b[2000005];
vector <int> sol;
const int mod1=100007,mod2=100021;
int hashf(int &p,char sir[],int l,int mod)
{
int h=0;
for(int i=0;i<l;i++)
{
if(i)
p=(p*256)%mod;
h=(h*256+sir[i])%mod;
}
return h;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",&a,&b);
int la=strlen(a),lb=strlen(b),p1=1,p2=1,o=0;
int h1a=hashf(p1,a,la,mod1),h1b=hashf(o,b,la,mod1);
int h2a=hashf(p2,a,la,mod2),h2b=hashf(o,b,la,mod2);
if(h1a==h1b&&h2a==h2b)
sol.push_back(1);
for(int i=la; i<lb; i++)
{
h1b=(((h1b-(p1*b[i-la])%mod1+mod1)%mod1)*256+b[i])%mod1;
h2b=(((h2b-(p2*b[i-la])%mod2+mod2)%mod2)*256+b[i])%mod2;
if(h1a==h1b&&h2a==h2b)
sol.push_back(i-la+1);
}
printf("%d\n",sol.size());
for(int i=0;i<min(1000,(int)sol.size());i++)
printf("%d ",sol[i]);
return 0;
}