Pagini recente » Cod sursa (job #53723) | Cod sursa (job #2532077) | Cod sursa (job #2128626)
#include <bits/stdc++.h>
using namespace std;
constexpr int P=73;
constexpr int MOD1=100007;
constexpr int MOD2=100021;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A,B;
vector<int>sol;
int main()
{
fin>>A>>B;
if(A.size()>B.size())
{
fout<<"0";
return 0;
}
int P1=1,P2=1;
int hashA1=0,hashA2=0;
for(int i=0;i<A.size();i++)
{
hashA1=(hashA1*P+A[i])%MOD1;
hashA2=(hashA2*P+A[i])%MOD2;
if(i!=0)
P1=(P1*P)%MOD1, P2=(P2*P)%MOD2;
}
int hash1=0,hash2=0;
for(int i=0;i<A.size();i++)
hash1=(hash1*P+B[i])%MOD1,
hash2=(hash2*P+B[i])%MOD2;
if(hash1==hashA1 && hash2==hashA2)
sol.push_back(1);
for(int i=A.size();i<B.size();i++)
{
hash1=((hash1-(B[i-A.size()]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
hash2=((hash2-(B[i-A.size()]*P2)%MOD2+MOD2)*P+B[i])%MOD2;
if(hash1==hashA1 && hash2==hashA2)
sol.push_back(i-A.size()+1);
}
fout<<sol.size()<<"\n";
for(auto i : sol)
fout<<i<<" ";
return 0;
}