Cod sursa(job #1081234)

Utilizator handz.FMI Andrei Tanasescu handz. Data 13 ianuarie 2014 13:24:03
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string.h>
using namespace std;

#define maxN 2000005
char T[maxN],P[maxN];
int n,m,v[maxN];

unsigned long power(int d,int m)
{
    int i;
    unsigned long p=1;
    for(i=1; i<m ;i++) p*=d;
    return p;
}

int EQ(char *P,char *T,int k)
{
    int i;
    for(i=0; i<m ;i++)
        if(P[i]!=T[k+i]) return 0;
    return 1;
}

int str_match(char *T,char *P,int d,int q)
{
    unsigned long h,p,t0;
    int i,k,nr=0;

    n=strlen(T); m=strlen(P);
    h=power(d,m)%q;
    p=0; t0=0;

    for(i=0; i<m ;i++)
    {
        p=(d*p+P[i])%q;
        t0=(d*t0+T[i])%q;
    }

    for(k=0; k<=n-m ;k++)
    {
        if(p==t0)
            if(EQ(P,T,k)) v[nr++]=k;
        t0=(t0+d*q-T[k]*h)%q;
        t0=(t0*d+T[k+m])%q;
    }
    if(nr>=0) return nr;
    else return -1;
}

int main()
{
    int i,poz;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s%s",P,T);
    poz=str_match(T,P,128,131);

    if(poz>=0)
    {
        printf("%d\n", poz);
        if(poz>1000)
        {
            for(i=0; i<1000 ;i++)
                printf("%d ",v[i]);
        }
        else
        {
            for(i=0; i<poz ;i++)
                printf("%d ",v[i]);
        }
    }
    else printf("%d\n", poz);
    fclose(stdout);
    return 0;
}