Cod sursa(job #2237849)

Utilizator andrei42Oandrei42O andrei42O Data 3 septembrie 2018 15:53:08
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,p;
int n,m,i,hs,hp,N,a[1024],rh(int, int, string);
bool verify(int, int);
int main()
{
    f>>p>>s;
    n=s.size();
    m=p.size();
    hp=rh(0,p.size(),p);
    for(i=m; i<n-m+1; i++)
    {
        hs=rh(i,i+m,s);
        if(hp==hs)
        {
            if(verify(i,i+m))
                N++,a[N]=i;
        }
    }
    g<<N<<'\n';
    for(i=1; i<=N; i++)
        g<<a[i]<<' ';

    return 0;
}
int rh(int start, int finish, string k)
{
    int j,ret=k[start];
    for(j=start+1; j<finish; j++)
    {
        ret=(ret%101)*256;
        ret+=k[j];
    }
    return ret%101;
}
bool verify(int start, int finish)
{
    int j;
    for(j=0; j<m; j++)
        if(p[j]!=s[i+j])
          return false;
    return true;
}