Pagini recente » Cod sursa (job #2333929) | Cod sursa (job #87100) | Cod sursa (job #585812) | Cod sursa (job #3274898) | Cod sursa (job #1427921)
#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;
long long ha, hb;
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; ++i)
{
if(ha==hb)
{
bool q=true;
for(j=0; j<a.length(); ++j)
if(a[j] != b[i+j]) q=false;
if(q){
if(s<1000)
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;
}