Cod sursa(job #1533134)

Utilizator radu_uniculeu sunt radu radu_unicul Data 22 noiembrie 2015 09:35:34
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<stdio.h>
#include<string.h>

#define d 256
char txt[2000001],pat[2000001],sol[2000001];
int nr;
void search(char pat[], char txt[], int q)
{
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0;
    int t = 0;
    int h = 1;

    for (i = 0; i < M-1; i++)
        h = (1LL*h*d)%q;
    for (i = 0; i < M; i++)
    {
        p = (1LL*d*p + pat[i])%q;
        t = (1LL*d*t + txt[i])%q;
    }

    for (i = 0; i <= N - M; i++)
    {

        if ( p == t )
        {
            /* Check for characters one by one */
            for (j = 0; j < M; j++)
            {
                if (txt[i+j] != pat[j])
                    break;
            }

            if (j == M)
                sol[++nr]=i;
        }
        if ( i < N-M )
        {
            t = (1LL*d*((t - 1LL*txt[i]*h)%q) + txt[i+M])%q;

            if (t < 0)
            t = (t + q);
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",&pat,&txt);
    int q = 100057;
    search(pat, txt, q);
    printf("%d\n",nr);
    for(int i=1;i<=nr;i++) printf("%d ",sol[i]);
    return 0;
}