Pagini recente » Cod sursa (job #1824801) | Cod sursa (job #451987) | Cod sursa (job #1500381) | Cod sursa (job #863355) | Cod sursa (job #3195015)
#include <fstream>
#include <cstring>
#include <vector>
#define MOD 100007
#define MOD1 100021
#define BASE 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long int y,z,hashA,hashA1,hashB,hashB1,p=1,p1=1,contor;
vector <int> A;
vector <int> B;
vector <int> ans;
char s[20000007];
int main()
{
fin>>s;
for(int j=0;s[j];j++)
{
if(isdigit(s[j]))
A.push_back(s[j]-'0');
else
if(islower(s[j]))
A.push_back(s[j]-'a'+10);
else
A.push_back(s[j]-'A'+36);
}
fin>>s;
for(int j=0;s[j];j++)
{
if(isdigit(s[j]))
B.push_back(s[j]-'0');
else
if(islower(s[j]))
B.push_back(s[j]-'a'+10);
else
B.push_back(s[j]-'A'+36);
}
int aux=A.size();
if(aux>B.size())
{
fout<<0;
return 0;
}
for(int i=0;i<aux;i++)
{
hashA=(hashA*BASE+A[i])%MOD;
hashA1=(hashA1*BASE+A[i])%MOD1;
hashB1=(hashB1*BASE+B[i])%MOD1;
hashB=(hashB*BASE+B[i])%MOD;
if(i!=0)
{
p=p*BASE%MOD;
p1=p1*BASE%MOD1;
}
}
if(hashA==hashB && hashA1==hashB1)
{
contor++;
ans.push_back(0);
}
for(int i=aux;i<B.size();i++)
{
hashB=((hashB-B[i-aux]*p%MOD+MOD)*BASE+B[i])%MOD;
hashB1=((hashB1-B[i-aux]*p1%MOD1+MOD1)*BASE+B[i])%MOD1;
if(hashB==hashA && hashB1==hashA1)
{
contor++;
if(contor<=1000)
{
ans.push_back(i-aux+1);
}
}
}
fout<<contor<<'\n';
for(int i=0;i<ans.size();i++)
fout<<ans[i]<<' ';
return 0;
}