Pagini recente » Cod sursa (job #950676) | Cod sursa (job #1853572) | Cod sursa (job #1395641) | Cod sursa (job #1597458) | Cod sursa (job #2732958)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long P=67, MOD=1000000009;
long long hash_b[2000001];
//int lps[2000001];
/*inline void getLPS(const string& a)
{ int j, i;
j=0;
for (i=1;i<a.size();)
if (a[i]==a[j])
{ ++j;
lps[i]=j;
++i;
}
else
if (j)
j=lps[j-1];
else
++i;
}
inline void getMatches(const string& a, const string& b)
{ vector<int> pos;
int cnt, i, j;
cnt=0;
pos.reserve(1000);
for (i=j=0;i<b.size();)
{ if (a[j]==b[i])
++i, ++j;
else
if (j)
j=lps[j-1];
else
++i;
if (j==a.size())
{ ++cnt;
if (pos.size()<1000)
pos.push_back(i-j);
j=lps[j-1];
}
}
fout<<cnt<<'\n';
for (i=0;i<pos.size();++i)
fout<<pos[i]<<' ';
}*/
int main()
{ ios::sync_with_stdio(false);
fin.tie(nullptr), fout.tie(nullptr);
int i, cnt;
long long curr_pow, hash_a;
string a, b;
vector<int> pos;
fin>>a>>b;
fin.close();
//getLPS(a);
//getMatches(a, b);
curr_pow=1;
hash_a=0;
for (i=0;i<a.size();++i)
{ hash_a=(hash_a+(a[i]-'0'+1)*curr_pow%MOD)%MOD;
curr_pow=curr_pow*P%MOD;
}
hash_b[0]=b[0]-'a'+1;
curr_pow=P;
for (i=1;i<b.size();++i)
{ hash_b[i]=(hash_b[i-1]+(b[i]-'0'+1)*curr_pow%MOD)%MOD;
curr_pow=curr_pow*P%MOD;
}
curr_pow=1;
cnt=0;
pos.reserve(1000);
for (i=0;i<(int)b.size()-(int)a.size();++i)
{ if (hash_a*curr_pow%MOD==(hash_b[i+a.size()-1]-(i?hash_b[i-1]:0)+MOD)%MOD)
{ ++cnt;
if (pos.size()<1000)
pos.push_back(i);
}
curr_pow=curr_pow*P%MOD;
}
fout<<cnt<<'\n';
for (i=0;i<pos.size();++i)
fout<<pos[i]<<' ';
fout.close();
return 0;
}