gistfile1.cpp

// Andrés Mejía
#include <cstring>
#include <iostream>
#include <vector>
#include <sys/time.h>
using namespace std;

const int MAXN = 1e9, MAXM = 10;
char d[MAXN+1];
char p[MAXM+1];

long currentMilliseconds() {
    timeval t;
    gettimeofday(&t, NULL);
    return t.tv_sec * 1000 + t.tv_usec / 1000;
}

void generateRandomString(char str[], int length) {
    for (int i = 0; i < length; ++i) {
        str[i] = 'a' + rand() % ('z' - 'a' + 1);
    }
    str[length] = '\0';
}

double score(int i, int m) {
    int equal = 0;
    for (int j = 0; j < m; ++j) {
        equal += (d[i + j] == p[j]);
    }
    return 1.0 * equal / m;
}

void findMatches(int n, int m, double tolerance) {
    long millisecondsBefore = currentMilliseconds();
    
    // Calculate matches and save them to memory
    vector< pair<int, double> > matches;
    for (int i = 0; i + m - 1 < n; ++i) {
        double s = score(i, m);
        if (s >= tolerance) {
            matches.push_back(make_pair(i, s));
        }
    }
    
    long elapsedMilliseconds = currentMilliseconds() - millisecondsBefore;
    
    // Print matches
    for (int i = 0; i < matches.size(); ++i) {
        printf("  position = %d, score = %lf (%.0lf characters are equal and %.0lf differ)\n",
                matches[i].first, matches[i].second, matches[i].second * m, (1 - matches[i].second) * m);
    }
    printf("Found %d matches in %ld milliseconds.\n", (int)matches.size(), elapsedMilliseconds);
}


int main() {
    int n = 1000000000, m = 9;
    if (n < 1 or n > MAXN or m < 1 or m > MAXM) {
        if (n < 1 or n > MAXN) printf("n must be between 1 and %d (it was %d)\n", MAXN, n);
        if (m < 1 or m > MAXM) printf("m must be between 1 and %d (it was %d)\n", MAXM, m);
        return 1;
    }
    generateRandomString(d, n);
    generateRandomString(p, m);

    // Uncomment the following two lines if you want to show the actual strings that were randomly generated
    //cout << d << endl;
    //cout << p << endl;
    
    findMatches(n, m, 0.6);
}
// Andrés Mejía