Pagini recente » Cod sursa (job #19701) | Rating Manolache Monica (Monina) | Istoria paginii utilizator/uwuenvy | Cod sursa (job #440115) | Cod sursa (job #1477824)
#include <bits/stdc++.h>
#define MOD1 103963
#define MOD2 100007
#define MOD3 100021
using namespace std;
string text,pattern;
bool lt[2000001];
int hash1,hash11,hash111,hash222,hash22,indexii2=1,indexii=1,indexii3=1,hash2,curr,a=73,b=73,c=73,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;
hash111=(hash111*c+pattern[i])%MOD3;
if(i!=0){
indexii=(indexii*a)%MOD1;
indexii2=(indexii2*b)%MOD2;
indexii3=(indexii3*c)%MOD3;
}
}
if(pattern.size()>text.size())
{
printf("0\n");
return 0;
}
for(int j=0;j<pattern.size();j++)
{
hash2=(hash2*a+text[j])%MOD1;
hash22=(hash22*b+text[j])%MOD2;
hash222=(hash222*c+text[j])%MOD3;
}
if(hash1==hash2 && hash11==hash22 && hash111==hash222)
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;
hash222=((hash222-(indexii3*text[j-pattern.size()])%MOD3+MOD3)*c+text[j])%MOD3;
//cout<<hash1<<" "<<hash2<<" "<<hash11<<" "<<hash22<<" "<<hash111<<" "<<hash222<<endl;
if(hash1==hash2 && hash11==hash22 && hash111==hash222)
lt[j-pattern.size()+1]=true,ans++;
}
cout<<ans<<"\n";
for(int j=0;j<text.size();j++)
if(lt[j])
cout<<j<<" ";
return 0;
}