Cod sursa(job #2136563)

Utilizator radurotaruRotaru Radu Stefan radurotaru Data 19 februarie 2018 23:13:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,i,j,q,p,t,h,e,d,v[1000001];
char a[2000001],c[2000001];
void RabinKarp( char a[], char c[], int q)
{
    m=strlen(a);
    n=strlen(c);
    p=0;
    t=0;
    h=1;
    for(i=0; i<m; i++)
    {
        h=(h*d)%q;
    }
    for(i=0; i<m; i++)
    {
        p=(d*p+a[i])%q;
        t=(d*t+c[i])%q;
    }
    for(i=0; i<=n-m; i++)
    {
        if(p==t)
        {
            for(j=0; j<m; j++)
            {
                if(c[i+j]!=a[j])
                    break;
            }
            if(j==m)
            {
                e++;
                v[e]=i;
            }
        }
        if(i<n-m)
        {
            t=(d*(t-c[i]*h)+ c[i+m])%q;
            if(t<0)
                t=t+q;
        }
    }
}
int main()
{
    f>>a;
    f>>c;
    q=101;
    if(strlen(a)<=strlen(c))
    RabinKarp( a,c,q);
    g<<e<<endl;
    for(i=1; i<=e; i++)
        g<<v[i]<<" ";
}