Cod sursa(job #1240347)

Utilizator mihai995mihai995 mihai995 Data 11 octombrie 2014 02:10:32
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <cstring>
using namespace std;

const int modList[] = {2, 7 + 1e9, 9 + 1e9}, base = 'z' - 'A' + 3;
const int N = 1 + 1e6;

char text[N], pattern[N];
bool match[N];

long long pow(long long a, int n, int mod){
    if (n < 2)
        return n == 1 ? a : 1;
    return pow(a * a % mod, n >> 1, mod) * pow(a, n & 1, mod) % mod;
}

int eval(char s[], int n, int mod){
    long long val = 0;
    for (int i = 0 ; i < n ; i++)
        val = ( val * base + (s[i] - 'A') ) % mod;
    return val;
}

void rabinKarp(char text[], char pattern[], int mod){
    int n = strlen(pattern);

    long long desiredVal = eval(pattern, n, mod), val = eval(text, n, mod), p = pow(base, n, mod);

    for (int i = 0 ; text[i + n - 1] ; i++){
        if (desiredVal != val)
            match[i] = false;
        val = ( (val * base + (text[i + n] - 'A') - (text[i] - 'A') * p) % mod + mod ) % mod;
    }
}

void patternMatch(char text[], char pattern[]){
    memset(match, true, sizeof(match));

    for (int i = 1 ; i <= modList[0] ; i++)
        rabinKarp(text, pattern, modList[i]);
}

int main(){
    ifstream in("strmatch.in");
    in >> pattern >> text;
    in.close();

    patternMatch(text, pattern);

    ofstream out("strmatch.out");

    int cntHits = 0, len = strlen(pattern) - 1;
    for (int i = 0 ; text[i + len] ; i++)
        if ( match[i] )
            cntHits++;

    out << cntHits << '\n';
    if (1000 < cntHits)
        cntHits = 1000;

    for (int i = 0 ; cntHits ; i++)
        if ( match[i] ){
            out << i << ' ';
            cntHits--;
        }
    out << '\n';

    out.close();

    return 0;
}