Cod sursa(job #1904671)

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

using namespace std;

inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
	unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
#ifdef __GNUC__
	asm(
		"divl %4; \n\t"
		: "=a" (d), "=d" (m)
		: "d" (xh), "a" (xl), "r" (y)
	);
#else
	__asm {
		mov edx, dword ptr[xh];
		mov eax, dword ptr[xl];
		div dword ptr[y];
		mov dword ptr[d], eax;
		mov dword ptr[m], edx;
	};
#endif
	out_d = d; out_m = m;
}

//x / y < 2^32 !
inline unsigned fasterLLMod(unsigned long long x, unsigned y) {
	unsigned dummy, r;
	fasterLLDivMod(x, y, dummy, r);
	return r;
}

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 = fasterLLMod((1LL * h1A * C1 + A[i]), MOD1);
        h2A = fasterLLMod((1LL * h2A * C2 + A[i]), MOD2);

        C1N = fasterLLMod((1LL * C1N * C1), MOD1);
        C2N = fasterLLMod((1LL * C2N * C2), MOD2);
    }

    vector <int> sol;

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

        if (i >= N + 1) {
            h1B = (h1B - fasterLLMod(1LL * B[i - N] * C1N, MOD1));
            if (h1B < 0)
                h1B += MOD1;
            h2B = (h2B - fasterLLMod(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;
}