Cod sursa(job #1904650)

Utilizator linia_intaiConstantinescu Iordache Ciobanu Noi cei din linia intai linia_intai Data 5 martie 2017 18:26:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

const int MOD1 = 1000000000 + 7;
const int C1 = 257;

//const int MOD2 = 1000000000 + 9;
//const int C2 = 263;

int N, M;
string A, B;

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");

    cin >> A >> B;
    N = A.size();
    M = B.size();

    if (N > M) {
        cout << "0\n";
        return 0;
    }

    A = " " + A;
    B = " " + B;

    int h1A = 0;
    int h2A = 0;
    int C1N = 1;
    int C2N = 1;

    for (int i = 1; i <= N; ++ i) {
        h1A = (1LL * h1A * C1 + A[i]) % MOD1;
        //h2A = (1LL * h2A * C2 + A[i]) % MOD2;

        C1N = (1LL * C1N * C1) % MOD1;
        //C2N = (1LL * C2N * C2) % MOD2;
    }

    vector <int> sol;

    int h1B = 0;
    int h2B = 0;
    for (int i = 1; i <= M; ++ i) {
        h1B = (1LL * h1B * C1 + B[i]) % MOD1;
        //h2B = (1LL * h2B * C2 + B[i]) % MOD2;

        if (i >= N + 1) {
            h1B = (h1B - 1LL * B[i - N] * C1N) % MOD1;
            if (h1B < 0)
                h1B += MOD1;
            //h2B = (h2B - 1LL * B[i - N] * C2N) % MOD2;
            //if (h2B < 0)
            //    h2B += MOD2;
        }

        if (i >= N && h1A == h1B)//&& h2A == h2B)
            sol.push_back(i - N);
    }

    cout << sol.size() << '\n';
    if (sol.empty())
        cout << '\n';
    else {
        cout << sol[0];
        for (int i = 1; i < 1000 && i < sol.size(); ++ i)
            cout << ' ' << sol[i];
        cout << '\n';
    }
    return 0;
}