Pagini recente » Cod sursa (job #493955) | Cod sursa (job #1918354) | Cod sursa (job #2848449) | Cod sursa (job #2535151) | Cod sursa (job #3194084)
#include <fstream>
#include <cstring>
#include <vector>
#define MOD 1000000007
#define MOD1 20000007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long int y,z,valA,valA1,valB,valB1,contor;
int baza61M[2000007];
int baza61M1[2000007];
vector <int> A;
vector <int> B;
vector <int> ans;
char s[20000007];
long long int updateA(int st,int dr);
long long int updateB(int st,int dr);
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;
}
baza61M[0]=1;
baza61M1[0]=1;
for(int i=1;i<=aux;i++)
{
baza61M[i]=61*baza61M[i-1]%MOD;
baza61M1[i]=61*baza61M1[i-1]%MOD1;
}
valA=updateA(0,aux-1);
for(int i=0;i<B.size()-aux+1;i++)
{
valB=updateB(i,i+aux-1);
if(valB==valA && valB1==valA1)
{
contor++;
if(contor<=1000)
{
ans.push_back(i);
}
}
}
fout<<contor<<'\n';
for(int i=0;i<ans.size();i++)
fout<<ans[i]<<' ';
return 0;
}
long long int updateA(int st,int dr)
{
long long int x=0;
valA1=0;
for(int i=st;i<=dr;i++)
{
x+=A[i]*baza61M[dr-st]%MOD;
valA1+=A[i]*baza61M1[dr-st]%MOD1;
}
return x;
}
long long int updateB(int st,int dr)
{
long long int x=0;
valB1=0;
for(int i=st;i<=dr;i++)
{
x+=B[i]*baza61M[dr-st]%MOD;
valB1+=B[i]*baza61M1[dr-st]%MOD1;
}
return x;
}