Pagini recente » Borderou de evaluare (job #1516346) | Borderou de evaluare (job #1590457) | Borderou de evaluare (job #1701777) | Cod sursa (job #2040352) | Cod sursa (job #490887)
Cod sursa(job #490887)
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
const char InFile[]="strmatch.in";
const char OutFile[]="strmatch.out";
const int MaxN=2005000;
const int MOD=32103110;
const int BASE=80;
ifstream fin(InFile);
ofstream fout(OutFile);
char A[MaxN],B[MaxN];
int n,Ahash,Bhash;
vector<int> pos;
inline int val(char ch)
{
if('0'<=ch && ch<='9')
{
return ch-'0';
}
if('a'<=ch && ch<='z')
{
return 11+ch-'a';
}
if('A'<=ch && ch<='Z')
{
return 38+ch-'A';
}
return BASE;
}
int main()
{
fin>>A>>B;
fin.close();
int lenA=strlen(A);
int lenB=strlen(B);
if(lenA>lenB)
{
fout<<"0";
fout.close();
return 0;
}
for(register int i=0;i<lenA;++i)
{
Ahash*=BASE;
Ahash+=val(A[i]);
Ahash%=MOD;
Bhash*=BASE;
Bhash+=val(B[i]);
Bhash%=MOD;
}
int BASEPA=1;
for(register int i=1;i<lenA;++i)
{
BASEPA*=BASE;
BASEPA%=MOD;
}
if(Ahash==Bhash)
{
if(pos.size()<1000)
{
pos.push_back(-1);
}
++n;
}
for(register int i=lenA;i<lenB;++i)
{
Bhash-=(BASEPA*val(B[i-lenA]))%MOD;
if(Bhash<0)
{
Bhash+=MOD;
}
Bhash*=BASE;
Bhash+=val(B[i]);
Bhash%=MOD;
if(Ahash==Bhash)
{
if(pos.size()<1000)
{
pos.push_back(i-lenA);
}
++n;
}
}
fout<<n<<"\n";
for(register int i=0;i<(int)pos.size();++i)
{
fout<<pos[i]+1<<" ";
}
fout.close();
return 0;
}