Pagini recente » Cod sursa (job #1189291) | Cod sursa (job #1336853) | Cod sursa (job #198531) | Cod sursa (job #193490) | Cod sursa (job #2909914)
#include <iostream>
#include<vector>
using namespace std;
const int mod=666013;
int hashfunction(string s)
{
int value=0, pow256=1;
for(int i=0; i<s.size(); i++)
{
value=(value+ pow256*s[s.size()-i-1])%mod;
pow256=(256*pow256)%mod;
}
return value;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string B="AnacalAna";
string A="Ana";
cin>>A>>B;
int hashvalA=hashfunction(A);
int hashval=hashfunction(B.substr(0,A.size()));
int p256=1;
for(int i=1; i<A.size(); i++)
{
p256=(256*p256)%mod;
}
vector <int> raspuns;
raspuns.resize(0);
if(hashval==hashvalA)raspuns.push_back(0);
for(int i=A.size(); i<B.size(); i++)
{
hashval=hashval-(p256*B[i-A.size()])%mod;
if (hashval<0) hashval+=mod;
hashval=(hashval*256+B[i])%mod;
if(hashval==hashvalA)raspuns.push_back(i-A.size()+1);
}
cout<<raspuns.size()<<endl;
for(int i=0; i<raspuns.size();i++)
cout<<raspuns[i]<<' ';
}