Cod sursa(job #1240354)

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

const int modList[] = {2, 7 + 1e4, 9 + 1e4}, base = 67;
const int N = 3 + 2e6;

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

inline int getVal(char c){
    return ind[c];
}

int pow(int 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){
    int val = 0;
    for (int i = 0 ; i < n ; i++)
        val = ( val * base + getVal( s[i] ) ) % mod;
    return val;
}

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

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

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

void patternMatch(char text[], char pattern[]){
    memset(ind, 0, sizeof(ind));

    int nr = 0;
    for (char c = 'a' ; c <= 'z' ; c++)
        ind[c] = nr++;
    for (char c = 'A' ; c <= 'Z' ; c++)
        ind[c] = nr++;
    for (char c = '0' ; c <= '9' ; c++)
        ind[c] = nr++;

    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;
    for (int i = 0 ; text[i] ; 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;
}