Pagini recente » Cod sursa (job #832357) | Cod sursa (job #1342390) | Cod sursa (job #1165048) | Cod sursa (job #1272244) | Cod sursa (job #1697809)
#include <bits/stdc++.h>
#define maxim 2000010
#define baza 73
using namespace std;
vector <int> poz;
char a[maxim],b[maxim];
unsigned int h[maxim],p[maxim];
unsigned int intr(int i,int j)
{
return h[i]-h[j+1]*p[j-i+1];
}
int main ()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
unsigned hasha=0;
int l1,l2,lim,ap=0,i;
f>>(a+1);
f>>(b+1);
l1=strlen(a+1);
l2=strlen (b+1);
p[0]=1;
for(i=1;i<=l2;++i)
{
p[i]=p[i-1]*baza;
}
for(i=l2;i>=1;i--)
{
h[i]=h[i+1]*baza+b[i];
}
for(i=l1;i>=1;i--)
{
hasha=hasha*baza+a[i];
}
lim=l2-l1+1;
for(i=1;i<=lim;i++)
{
if(intr(i,i+l1-1)==hasha)
{
++ap;
if(ap<=1000)
poz.push_back (i-1);
}
}
g<<ap<<'\n';
for(auto x:poz)
g<<x<<' ';
return 0;
}