Cod sursa(job #1519737)

Utilizator valentinpielePiele Valentin valentinpiele Data 7 noiembrie 2015 19:24:01
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <cstring>
#define mod1 100007
#define mod2 666013
#define factor 123
using namespace std;

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

const int Nmax = 2000010;
char str1[Nmax], str2[Nmax];

int match[Nmax];
int N, M;

int vstr1mod1, vstr1mod2;
int vstr2mod1, vstr2mod2;
int putere1, putere2;
int contor;

int x, y;

int main ()
{
    f.get(str1, sizeof(str1));
    f.get();
    f.get(str2, sizeof(str2));

    N = strlen(str1);
    M = strlen(str2);

    if(N > M) { g << '0' << '\n'; return 0;}
    putere1 = putere2 = 1;
    vstr1mod1 = vstr1mod2 = vstr2mod1 = vstr2mod2 = 0;

    for(int i = 0; i < N; i ++)
    {
        vstr1mod1 = (vstr1mod1 * factor + str1[i]) % mod1;
        vstr1mod2 = (vstr1mod2 * factor + str1[i]) % mod2;
        if(i != 0)
        {
            putere1 = (putere1 * factor) %mod1;
            putere2 = (putere2 * factor) %mod2;
        }
    }

    for(int i = 0; i < N; i ++)
    {
        vstr2mod1 = (vstr2mod1 * factor + str2[i]) % mod1;
        vstr2mod2 = (vstr2mod2 * factor + str2[i]) % mod2;
    }

    if(vstr1mod1 == vstr2mod1 && vstr1mod2 == vstr2mod2) { contor ++; match[0] = 1; }

    for(int i = N; i < M; i ++)
    {
        x = (putere1 * str2[i - N]) % mod1;
        y = (putere2 * str2[i - N]) % mod2;

        vstr2mod1 -= x;
        vstr2mod2 -= y;

        if(vstr2mod1 < 0) vstr2mod1 += mod1;
        if(vstr2mod2 < 0) vstr2mod2 += mod2;

        vstr2mod1 = (vstr2mod1 * factor + str2[i + N - 1]) % mod1;
        vstr2mod2 = (vstr2mod2 * factor + str2[i + N - 1]) % mod2;

        if(vstr1mod1 == vstr2mod1 && vstr1mod2 == vstr2mod2) { match[i - N +1] = 1; contor ++; }

    }

    g << contor << '\n';
    contor = 0;
    for(int i = 0; i < M && contor < 1000; i ++)
        if(match[i]) { contor ++, g << i << ' ';}
    g << '\n';

    return 0;
}