Cod sursa(job #1240349)

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

const int modList[] = {2, 7 + 1e9, 9 + 1e9}, base = 57;
const int N = 1 + 2e6;

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

inline int getVal(char c){
    return c <= 'Z' ? c - 'A' : c - 'a' + 27;
}

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 + getVal( s[i] ) ) % 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 + getVal( text[i + n] ) - getVal( text[i] ) * 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;
}