Pagini recente » Cod sursa (job #291138) | Cod sursa (job #398465) | Cod sursa (job #131435) | Cod sursa (job #2816864) | Cod sursa (job #1702314)
#include <bits/stdc++.h>
using namespace std;
#define lmax 2000010
const unsigned int BAZA = 71;
#define f cin
#define g cout
vector<int>pozsir;
char A[lmax],B[lmax];
unsigned int p[lmax],h[lmax],la,lb,hasha,ap,i,j;
int lim;
unsigned int hashinterval(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);
la=strlen(A+1);
lb=strlen(B+1);
lim=lb-la+1;
p[0]=1;
for(i=1;i<=lb;i++)
{
p[i]=p[i-1]*BAZA;
}
for(i=lb;i>=1;i--)
{
h[i]=h[i+1]*BAZA+B[i];
}
for(i=la;i>=1;i--)
{
hasha=hasha*BAZA+A[i];
}
for(i=1;i<=lim;i++)
{
if(hashinterval(i,i+la-1)==hasha)
{
ap++;
if(ap<=1000)
pozsir.push_back(i-1);
}
}
g<<ap<<'\n';
for(int i = 0 ;i < pozsir.size() ; ++i)
g<<pozsir[i]<<" ";
return 0;
}