Cod sursa(job #873088)

Utilizator TeOOOVoina Teodora TeOOO Data 6 februarie 2013 21:07:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <stdio.h>
#include <string.h>
using namespace std;

//Constante
const int sz = (int)2e6 + 1;
const int mod1 = 20007;
const int mod2 = 20021;
const int P = 73;

//Variabile
FILE *in,*out;

char sub[sz], str[sz];

int subHash1, subHash2;
int strHash1, strHash2;
int P1=1, P2=1;

int answer;
int answers[1001];

int main()
{
    in=fopen("strmatch.in","rt");
    out=fopen("strmatch.out","wt");

    fscanf(in,"%s",sub);
    fscanf(in,"%s",str);

    int subLen = strlen(sub);
    int strLen = strlen(str);

    subHash1 = subHash2 = (int)sub[0];
    strHash1 = strHash2 = (int)str[0];

    for(int i=1; i<subLen; ++i)
    {
        subHash1 = (subHash1 * P + sub[i]) % mod1;
        subHash2 = (subHash2 * P + sub[i]) % mod2;
        strHash1 = (strHash1 * P + str[i]) % mod1;
        strHash2 = (strHash2 * P + str[i]) % mod2;
        P1 = (P1*P) % mod1;
        P2 = (P2*P) % mod2;
    }

    if(subHash1 == strHash1 && subHash2 == strHash2)
    {
        ++answer;
       // if(answer <= 1000)
       //     answers[answer] = 0;
    }

    for(int i=subLen; i<strLen; ++i)
    {
        strHash1 = ((strHash1 - str[i-subLen]*P1) % mod1) + mod1;
        strHash1 = (strHash1*P + str[i]) % mod1;
        strHash2 = ((strHash2 - str[i-subLen]*P2) % mod2) + mod2;
        strHash2 = (strHash2*P + str[i]) % mod2;
        if(subHash1 == strHash1 && subHash2 == strHash2)
        {
            ++answer;
            if(answer <= 1000)
                answers[answer] = i-subLen+1;
        }
    }

    fprintf(out, "%d\n",answer);
    if(answer <= 1000)
        for(int i=1; i<=answer; ++i)
            fprintf(out,"%d ",answers[i]);
    else
        for(int i=1; i<=1000; ++i)
            fprintf(out,"%d ", answers[i]);

    fclose(in);
    fclose(out);
    return 0;
}