Pagini recente » Istoria paginii utilizator/uwuenvy | Cod sursa (job #440115) | Cod sursa (job #1477824) | Cod sursa (job #437465) | Cod sursa (job #1477812)
#include <bits/stdc++.h>
#define MOD1 100007
using namespace std;
string text,pattern;
bool lt[2000001];
int hash1,index=1,hash2,curr,a=107,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+int(pattern[i]))%MOD1;
if(i!=0)
index=(index*a)%MOD1;
}
for(int j=0;j<pattern.size();j++)
{
hash2=(hash2*a+int(text[j]))%MOD1;
}
if(hash1==hash2)
lt[0]=true,ans++;
for(int j=pattern.size();j<text.size();j++)
{
hash2=((hash2-(index*int(text[j-pattern.size()]))%MOD1+MOD1)*a+int(text[j]))%MOD1;
//cout<<hash1<<" "<<hash2<<endl;
if(hash1==hash2)
lt[j-pattern.size()+1]=true,ans++;
}
cout<<ans<<"\n";
for(int j=0;j<2000001;j++)
if(lt[j])
cout<<j<<" ";
return 0;
}