Cod sursa(job #1477812)

Utilizator ggokGeri Gokaj ggok Data 27 august 2015 02:18:15
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#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;
}