Pagini recente » Cod sursa (job #1408076) | Cod sursa (job #1455525) | Cod sursa (job #391789) | Cod sursa (job #490368) | Cod sursa (job #1477821)
#include <bits/stdc++.h>
#define MOD1 103963
#define MOD2 100019
using namespace std;
string text,pattern;
bool lt[2000001];
int hash1,hash11,hash22,indexii2=1,indexii=1,hash2,curr,a=73,b=167,ans;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin>>pattern>>text;
for(int i=0;i<pattern.size();i++){
hash1=(hash1*a+pattern[i])%MOD1;
hash11=(hash11*b+pattern[i])%MOD2;
if(i!=0){
indexii=(indexii*a)%MOD1;
indexii2=(indexii2*b)%MOD2;
}
}
if(pattern.size()>text.size())
{
printf("0");
return 0;
}
for(int j=0;j<pattern.size();j++)
{
hash2=(hash2*a+text[j])%MOD1;
hash22=(hash22*b+text[j])%MOD2;
}
if(hash1==hash2 && hash11==hash22)
lt[0]=true,ans++;
for(int j=pattern.size();j<text.size();j++)
{
hash2=((hash2-(indexii*text[j-pattern.size()])%MOD1+MOD1)*a+text[j])%MOD1;
hash22=((hash22-(indexii2*text[j-pattern.size()])%MOD2+MOD2)*b+text[j])%MOD2;
//cout<<hash1<<" "<<hash2<<endl;
if(hash1==hash2 && hash11==hash22)
lt[j-pattern.size()+1]=true,ans++;
}
cout<<ans<<"\n";
for(int j=0;j<2000001;j++)
if(lt[j])
cout<<j<<" ";
return 0;
}