Pagini recente » Cod sursa (job #2514633) | Cod sursa (job #18873) | Cod sursa (job #1011842) | Cod sursa (job #612518) | Cod sursa (job #2058787)
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#define B1 69
#define B2 97
#define M1 11243567
#define M2 19898746
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
string a,b;
vector<int> v;
int r,r1,r2,r3,r4,p1,p2;
int to_int(char c)
{
if('0'<=c && c<='9') return (c-'0')+1;
if('A'<=c && c<='Z') return (c-'A')+11;
if('z'<=c && c<='z') return (c-'a')+36;
//am 10+25+25 caractere si inca 1 sa scap de 0 (61)
}
int main()
{
int i,j,ind;
fin>>a>>b;
p1=p2=1;
for(i=0;i<a.size();i++)
{
if(i>0) p1=(p1*B1)%M1;
if(i>0) p2=(p2*B2)%M2;
r1=(r1*B1+to_int(a[i]))%M1;
r2=(r2*B2+to_int(a[i]))%M2;
}
for(i=0;i<a.size()-1;i++)
{
r3=((r3*B1)+to_int(b[i]))%M1;
r4=((r4*B2)+to_int(b[i]))%M2;
}
for(i=a.size()-1;i<b.size();i++)
{
ind=i-a.size()+1;
r3=((r3*B1)+to_int(b[i]))%M1;
r4=((r4*B2)+to_int(b[i]))%M2;
if(r3==r1 && r4==r2)
{
r++;
v.push_back(ind);
}
r3=(((r3-p1*to_int(b[ind]))%M1)+M1)%M1;
r4=(((r4-p2*to_int(b[ind]))%M2)+M2)%M2;
}
fout<<r<<"\n";
if(r>1000) r=1000;
for(i=0;i<r;i++)
{
fout<<v[i]<<" ";
}
}