Cod sursa(job #2085038)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 9 decembrie 2017 16:23:01
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

inline void debugMode() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    #ifndef ONLINE_JUDGE
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    #endif // ONLINE_JUDGE
}
inline void PrintYes() { cout << "Yes"; }
inline void PrintNo() { cout << "No"; }

const double eps = 1e-7;
const int Nmax = 2e6 + 1;
const int prime_number = 101;

int index[Nmax];
int ans;

void Rabin_Karp(string pat, string txt)
{
    int h = 1;
    int N, M;

    M = (int)pat.size();
    N = (int)txt.size();

    ///h = 256^(M-1)
    for(int i = 0; i < M - 1; ++i)
        h = (h * 256) % prime_number;

    int hash_pat = 0; /// hash value pentru pattern
    int hash_txt = 0; /// hash value pentru text

    /// hash value pentru pattern si respectiv pria subsecventa din text
    for(int i = 0; i < M; ++i) {
        hash_pat = (256 * hash_pat + pat[i]) % prime_number;
        hash_txt = (256 * hash_txt + txt[i]) % prime_number;
    }

    int j;
    for(int i = 0; i <= N - M; ++i) {
        /// daca au aceeasi valoare a hash-urilor
        if(hash_pat == hash_txt) {
            for(j = 0; j < M; ++j) /// verific sa fie intr-adevar acelasi string
                if(txt[i + j] != pat[j]) /// inseamnca nu sunt la fel si nu mai continui
                    break;

            if(j == M) { /// verific daca sunt aceleasi string-uri
                ans++;
                index[ans] = i;
            }
        }
        /// recalculez urmatoarea valoare a hash-ului pentru stringul txt[i+1...i+M]
        if(i < N - M) {
            hash_txt = (256 * (hash_txt - txt[i] * h) + txt[i + M]) % prime_number;
            if(hash_txt < 0)
                hash_txt += prime_number;
        }
    }

}


int main()
{
	debugMode();

    string pat, txt;

    cin >> pat >> txt;

    Rabin_Karp(pat, txt);

    cout << ans << '\n';
    for(int i = 1; i <= ans; ++i)
        cout << index[i] << " ";

	return 0;
}