Pagini recente » Cod sursa (job #2422439) | Cod sursa (job #1573607) | Cod sursa (job #245534) | Cod sursa (job #169485) | Cod sursa (job #3258202)
#include <iostream>
#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int MOD1=1e9+7,MOD2=1e9+13;
int p1=31,p2=37;
vector <int> ans;
string s1,s2;
int n,v;
int32_t main()
{
fin>>s1;
int has1=0,pow1=1,has12=0,pow2=1;
for (int i=0; i<s1.size(); i++)
{
has1=has1*p1%MOD1+s1[i];
has1%=MOD1;
if(i) pow1*=p1,pow1%=MOD1;
has12=has12*p2%MOD2+s1[i];
has12%=MOD2;
if(i) pow2*=p2,pow2%=MOD2;
}
//cout<<pow1<<' '<<has1<<'\n';
fin>>s2;
int has2=0,has22=0;
for (int i=0; i<s1.size(); i++)
{
has2=has2*p1%MOD1+s2[i];
has2%=MOD1;
has22=has22*p2%MOD2+s2[i];
has22%=MOD2;
}
if (has1==has2 && has12==has22) ans.push_back(0);
for (int i=s1.size(); i<s2.size(); i++)
{
has2=(p1*((has2+MOD1-(s2[i-s1.size()]*pow1%MOD1))%MOD1)+s2[i])%MOD1;
has22=(p2*((has22+MOD2-(s2[i-s1.size()]*pow2%MOD2))%MOD2)+s2[i])%MOD2;
if (has2==has1) ans.push_back(i-s1.size()+1);
}
fout<<ans.size()<<'\n';
for (int i=0; i<ans.size() && i<=1000; i++)
fout<<ans[i]<<' ';
return 0;
}