Cod sursa(job #1779766)

Utilizator antracodRadu Teodor antracod Data 15 octombrie 2016 16:34:45
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int NMAX = 2000002;

char pattern[NMAX];
char text[NMAX];
int sol[NMAX];
int prime=101;
int d=256;
int k=0;
void rabinkarp(int n,int m)
{

    int hashpat = 0;
    int hashtxt = 0;
    int pow = 1;
    int i,j;

    for(i=0; i<n-1; i++)
    {
        pow=(pow*d)%prime;
    }


    for(i=0; i<n; i++)
    {
        hashpat=(hashpat*d + pattern[i])%prime;
        hashtxt=(hashtxt*d + text[i])%prime;
    }

    for(i=0; i<=m-n; i++)
    {
        if(hashpat==hashtxt)
        {
            for(j=0; j<n; j++)
            {
                if(pattern[j]!=text[i+j])
                    break;
            }
            if(j==n)
            {
                sol[k]=i;
                k++;
            }
        }
        if(i<m-n)
        {
            hashtxt=(d*(hashtxt-text[i]*pow)+text[i+n])%prime;
            if(hashtxt<0)
                hashtxt=hashtxt+prime;
        }
    }

}

int main()
{
    in>>pattern;
    in>>text;

    int n = strlen(pattern);
    int m = strlen(text);

    if(n>m)
        {
            out<<0;
            return 0;
        }

    rabinkarp(n,m);
    out<<k<<'\n';
    for(int i=0;i<k && i<1000;i++)
    {
        out<<sol[i]<<" ";
    }

}