Pagini recente » Cod sursa (job #1355352) | Cod sursa (job #2756530) | Cod sursa (job #563020) | Cod sursa (job #1960013) | Cod sursa (job #3137382)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int P=666013;
const int Q=1000000007;
inline prod(int X,int Y){X=1LL*X*Y%Q;return X;}
inline suma(int X,int Y){X=(X+Y)%Q;return X;}
inline diff(int X,int Y){X=(X-Y+Q)%Q;return X;}
string a,b;
int cnt;
vector<int> sol;
int main()
{
f>>a>>b;
int n=a.size(),m=b.size();
/// calculez valoarea hash pentru a
int p=1;
int valA=a[0];
for(int i=1;i<n;i++)
{
p=prod(p,P);/// aici calulez p=P^(n-1)
valA=suma(prod(valA,P),int(a[i]));/// aici calculez valoarea asociata lui a
}
int valB=b[0];
for(int i=1;i<n-1;i++)
valB=suma(prod(valB,P),b[i]);
for(int st=0,dr=n-1;dr<m;st++,dr++)
{
valB=suma(prod(valB,P),int(b[dr]));
if(valA==valB)
{
cnt++;
if(cnt<=1000)
sol.push_back(st);
}
valB=diff(valB,prod(p,int(b[st])));
}
g<<cnt<<'\n';
for(auto it:sol)
g<<it<<' ';
return 0;
}