Cod sursa(job #1984004)

Utilizator OFY4Ahmed Hamza Aydin OFY4 Data 23 mai 2017 12:18:23
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int mod1 = 100007, mod2 =666013, p =79;
int sol[1007], n2, n1, p1, p2, hash1, hash2, hashv1, hashv2, nr;
char v1[2000007], v2[2000007];

int main()
{
    in >> v1 >> v2;
    n1 = strlen(v1);
    n2 = strlen(v2);
    if(n1 > n2)
    {
        out << "0";
        return 0;
    }
    for(int i = 0; i < n1; ++i)
    {
        hashv1 = (hashv1 * p + v1[i]) % mod1;
        hashv2 = (hashv2 * p + v1[i]) % mod2;
        hash1 = (hash1 * p + v2[i]) % mod1;
        hash2 = (hash2 * p + v2[i]) & mod2;
    }
    p1 = p2 = 1;
    for(int i = 1; i < n1; ++i)
    {
        p1 = (p1 * p) % mod1;
        p2 = (p2 * p) % mod2;
    }
    if(hash1 == hashv1 && hash2 == hashv2)
        sol[++nr] = 0;
    for(int i = n1; i < n2; ++i)
    {
        hash1 = ((hash1 - (p1 * v1[i - n1]) % mod1 + mod1) * p + v1[i]) % mod1;
        hash2 = ((hash2 - (p2 * v2[i - n2]) % mod2 + mod2) * p + v1[i]) % mod2;

        if(hash1 == hashv1 && hash2 == hashv2)
        {
            nr++;
            if(nr <= 1000)
                sol[nr] = i - n1 + 1;
        }
    }

    out << nr << "\n";
    if(nr > 1000)
        nr = 1000;
    for(int i = 1; i <= nr; ++i)
        out << sol[i] << " ";
    return 0;
}