Pagini recente » Cod sursa (job #3261780) | Cod sursa (job #2596665) | Cod sursa (job #2593562) | Cod sursa (job #2896621) | Cod sursa (job #2593557)
#include <bits/stdc++.h>
using namespace std;
/*****************************************/
const int m1=100007;
const int m2=100021;
const int p=101;
string A;
string B;
int nA;
int nB;
int hash1,hash2,h1,h2;
int rasp;
int p1=1,p2=1;
bool nuVerifica=false;
int v[2000001];
/*****************************************/
ifstream f("strmatch.in");
ofstream g("strmatch.out");
/*****************************************/
///--------------------------------------------------
inline void readInput()
{
f>>A>>B;
nA=A.length();
nB=B.length();
}
///--------------------------------------------------
inline void creeareHashA()
{
for(int i=0;i<nA;i++)
{
hash1=hash1*p%m1 + A[i];
hash2=hash2*p%m2 + A[i];
if(i!=0)
{
p1=p1*p%m1;
p2=p2*p%m2;
}
}
if(nA>nB) nuVerifica=true;
}
///--------------------------------------------------
inline void creeareHashB()
{
for(int i=0;i<nA;i++)
{
h1=h1*p%m1+B[i];
h2=h2*p%m2+B[i];
}
if(hash1==h1 && hash2==h2)
{
rasp++;
v[0]=1;
}
}
///--------------------------------------------------
inline void Comparare()
{
for(int i=nA;i<nB;i++)
{
h1=((h1-B[i-nA]*p1%m1+m1)*p+B[i])%m1;
h2=((h2-B[i-nA]*p2%m2+m2)*p+B[i])%m2;
if(hash1==h1 && hash2==h2)
{
v[i-nA+1]=1;
rasp++;
}
}
}
///--------------------------------------------------
inline void Afisare()
{
g<<rasp<<"\n";
for(int i=0;i<nB;i++)
{
if(v[i]==1) g<<i<<" ";
}
}
///--------------------------------------------------
inline void Solution()
{
creeareHashA();
if(nuVerifica==true)
{
g<<"0"<<"\n";
return;
}
creeareHashB();
Comparare();
Afisare();
}
///--------------------------------------------------
int main()
{
readInput();
Solution();
return 0;
}