Cod sursa(job #1519716)

Utilizator valentinpielePiele Valentin valentinpiele Data 7 noiembrie 2015 19:04:33
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <cstring>
#define mod1 10007
#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[1001];
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);

    putere1 = putere2 = 1;

    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[contor] = 0; }

    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]) % mod1;
        vstr2mod2 = (vstr2mod2 * factor + str2[i]) % mod2;

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

    }

    g << contor << '\n';
    for(int i = 0; i < 1001; i ++) if(match[i] != 0) g << match[i] << ' ';
    g << '\n';

    return 0;
}