Cod sursa(job #1477819)

Utilizator ggokGeri Gokaj ggok Data 27 august 2015 02:32:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#define MOD1 100007
#define MOD2 100021
using namespace std;
string text,pattern;
bool lt[2000001];
int hash1,hash11,hash22,indexii2=1,indexii=1,hash2,curr,a=73,b=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+int(pattern[i]))%MOD1;
hash11=(hash11*b+int(pattern[i]))%MOD2;
if(i!=0){
indexii=(indexii*a)%MOD1;
indexii2=(indexii2*b)%MOD2;
}
}
for(int j=0;j<pattern.size();j++)
{
    hash2=(hash2*a+int(text[j]))%MOD1;
    hash22=(hash22*b+int(text[j]))%MOD2;
}
if(hash1==hash2 && hash11==hash22)
lt[0]=true,ans++;
for(int j=pattern.size();j<text.size();j++)
{
hash2=((hash2-(indexii*int(text[j-pattern.size()]))%MOD1+MOD1)*a+int(text[j]))%MOD1;
hash22=((hash22-(indexii2*int(text[j-pattern.size()]))%MOD2+MOD2)*b+int(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;
}