Pagini recente » Cod sursa (job #1373651) | Cod sursa (job #2072734) | Cod sursa (job #1512726) | Cod sursa (job #1192231) | Cod sursa (job #1427909)
#include<fstream>
#include<string>
#include<sstream>
#define MOD 3
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i,j,s;
stringstream result;
string a,b;
unsigned long long ha, hb;
unsigned long long pow(int n, int p)
{
unsigned long long a=n;
unsigned long long sol=1;
for(int i=0; (1<<i) <= p; ++i)
{
if(((1<<i)&p) > 0)
sol=sol*a;
a=a*a;
}
return sol;
}
int main()
{
fin>>a;
fin>>b;
for(i=0; i<a.length(); ++i)
ha+=pow(MOD,a.length()-i-1)*a[i];
for(i=0; i<a.length(); ++i)
hb+=pow(MOD,a.length()-i-1)*b[i];
for(i=0; i<b.length()-a.length()+1 && s<1000; ++i)
{
if(ha==hb)
{
bool q=true;
for(j=0; j<a.length(); ++j)
if(a[j] != b[i+j]) q=false;
if(q)
result<<i<<" ", s++;
}
hb=MOD*(hb-pow(MOD, a.length()-1)*b[i]) + b[i+a.length()];
}
fout<<s<<endl;
fout<<result.str();
return 0;
}