Cod sursa(job #1904666)

Utilizator cristicretancristi cretan cristicretan Data 5 martie 2017 18:36:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>
#define NMax 200001
#define INF 0x3f3f3f3f
using namespace std;

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

const int a = 73;
const int b = 7;

const int mod1 = 100007;
const int mod2 = 100021;

char X[NMax], Y[NMax];
int hash1, hash2;
int H1, H2;
vector<int> ans;

int main()
{
    f.getline(X, NMax);
    f.getline(Y, NMax);

    int x = strlen(X);
    int y = strlen(Y);

    int A = 1, B = 1;

    for(int i = x - 1; i >= 0; --i)
    {
        if(i == x - 1)
        {
            H1 = X[i];
            H2 = X[i];
            hash1 = Y[i];
            hash2 = Y[i];
            continue;
        }

        A *= a; B *= b; A %= mod1; B %= mod2;

        H1 += A * X[i]; H1 %= mod1;
        H2 += B * X[i]; H2 %= mod2;

        hash1 += A * Y[i]; hash1 %= mod1;
        hash2 += B * Y[i]; hash2 %= mod2;
    }

    int t = 0;
    for(int i = x; i < y; ++i)
    {
        if(hash1 == H1 && hash2 == H2)
        {
            ++t;
            if(ans.size() < 1000)
                ans.push_back(i - 1);
        }

        hash1 = (hash1 - (Y[i - x] * A) % mod1 + mod1) % mod1;
        hash1 = hash1 * a;
        hash1 = hash1 + Y[i];
        hash1 %= mod1;

        hash2 = (hash2 - (Y[i - x] * B) % mod2 + mod2) % mod2;
        hash2 = hash2 * b;
        hash2 = hash2 + Y[i];
        hash2 %= mod2;
    }
    if(hash1 == H1 && hash2 == H2)
    {
        ++t;
        if(t < 1000)
            ans.push_back(y - 1);
    }
    g << t << '\n';
    for(int i = 0; i < ans.size(); ++i)
        g << ans[i] - x + 1 << " ";
    return 0;
}