Pagini recente » Cod sursa (job #891967) | Cod sursa (job #34327) | Cod sursa (job #59104) | Cod sursa (job #1219243) | Cod sursa (job #2042500)
#include <fstream>
#include <cstring>
#include <vector>
#define MAX 2000005
#define PRIM 1000000007LL
#define LL long long
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char A[MAX],B[MAX];
int a,b;
int n;
vector <LL> rez;
int cod(char c)
{
if ('a'<=c && c<='z')
return c-'a';
if ('A'<=c && c<='Z')
return c-'A'+26;
if ('0'<=c && c<='9')
return c-'0'+52;
}
int main()
{
fi>>A+1>>B+1;
a=strlen(A+1),b=strlen(B+1);
if (a>b)
{
fo<<0;
return 0;
}
LL v=1; ///62^(a-1)
for (int i=1; i<a; i++)
{
v=(1LL*v*62)%PRIM;
}
LL nr=0,vhash=0;
for (int i=1; i<=a; i++)
{
nr=(1LL*nr*62+cod(A[i]))%PRIM;
vhash=(1LL*vhash*62+cod(B[i]))%PRIM;
}
for (int sf=a; sf<=b; sf++)
{
if (nr==vhash)
{
n++;
rez.push_back(sf-a);
}
vhash=(PRIM+vhash-1LL*v*cod(B[sf-a+1]))%PRIM;
vhash=(1LL*vhash*62+cod(B[sf+1]))%PRIM;
}
fo<<n<<"\n";
for (int i=0; i<min(n,1000); i++)
fo<<rez[i]<<" ";
return 0;
}