Pagini recente » Cod sursa (job #721760) | Cod sursa (job #633914) | Cod sursa (job #2672372) | Cod sursa (job #43849) | Cod sursa (job #1697798)
#include <bits/stdc++.h>
#define maxim 2000010
#define baza 70
using namespace std;
int l1,l2,lim,ap;
vector <int> poz;
char a[maxim],b[maxim];
unsigned h[maxim],p[maxim],hasha,i;
unsigned 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");
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;
}