Pagini recente » Cod sursa (job #771475) | Cod sursa (job #697814) | Cod sursa (job #1901344) | Cod sursa (job #1800890) | Cod sursa (job #2526079)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
int nr=0;
const ll MOD=1000000007,A=69420911;
ll hashA;
vector<ll>powA;
vector<ll>hashB;
vector<int>sol;
void makeHashA()
{
for(auto c:a)
hashA=(hashA*A+c)%MOD;
}
void makeHashB()
{
hashB.push_back(b[0]);
for(int i=1;i<b.size();i++)
hashB.push_back((hashB[i-1]*A+b[i])%MOD);
}
void makePowA(int length)
{
powA.push_back(1);
for(int i=1;i<=length;i++)
powA.push_back((powA[i-1]*A)%MOD);
}
ll getHash(int i,int j)
{
return (!i)?
hashB[j]:
(hashB[j]-(hashB[i-1]*powA[j-i+1])%MOD+MOD)%MOD;
}
void solve()
{
for(int i=0;i<b.size()-a.size();i++)
if(getHash(i,i+a.size()-1)==hashA)
{
sol.push_back(i);
nr++;
}
}
int main()
{
in>>a>>b;
makeHashA();
makeHashB();
makePowA(b.size());
solve();
out<<nr<<'\n';
for(auto x:sol)
out<<x<<' ';
return 0;
}