Cod sursa(job #2045856)

Utilizator enedumitruene dumitru enedumitru Data 22 octombrie 2017 22:34:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
/*
#include <bits/stdc++.h>
using namespace std;
ifstream f ("strmatch.in"); ofstream fout ("strmatch.out");
unsigned int x=71,ha,p[2000002],hb[2000002];
char a[2000002],b[2000002];
int nr,v[1002];
void rabin_karp()
{   int n=strlen(a),m=strlen(b);
    for(int i=n-1;i>=0;--i) ha=ha*x+a[i];
    for(int i=m-1;i>=0;--i) hb[i]=hb[i+1]*x+b[i];
    p[0]=1;
    for(int i=1;i<=m;++i) p[i]=p[i-1]*x;
    for(int i=n-1;i<m;++i )
    {   if(ha==hb[i-n+1]-hb[i+1]*p[n])
        {  if(nr<1000) v[++nr]=i-n+1;}
    }
}
int main()
{   f>>a>>b;
    rabin_karp();
    fout<<nr<<'\n';
    for(int i=1;i<=nr;++i) fout<<v[i]<<" ";
    fout.close(); return 0;
}
*/
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in"); ofstream fout("strmatch.out");
vector <int> rez;
unsigned int p[2000002],x=71,ha,hb[2000002];
char A[2000002], B[2000002];
int cnt;
void rabin_karp()
{
    int n=strlen(A),m=strlen(B);
    for(int i=n-1;i>=0;--i) ha=ha*x+A[i];
    for(int i=m-1;i>=0;--i) hb[i]=hb[i+1]*x+B[i];
    p[0]=1;
    for(int i=1;i<=m;++i) p[i]=p[i-1]*x;
    for(int i=n-1;i<m;++i )
    {   if(ha==hb[i-n+1]-hb[i+1]*p[n])
        {   cnt++;
            if(cnt<=1000) rez.push_back(i-n+1);
        }
    }
}
int main()
{   fin>>A>>B;
    rabin_karp();
    fout<<cnt<<'\n';
    vector <int> :: iterator it=rez.begin(), sf=rez.end();
    for(;it!=sf;++it) fout<<*it<<" ";
}