Cod sursa(job #2237856)

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

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