Cod sursa(job #878149)

Utilizator dan.lincanDan Lincan dan.lincan Data 14 februarie 2013 02:56:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>

using namespace std;

void redirectInput(const char *in, const char *out)
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
}

void printVector(vector<int> &v, int size)
{
    for(int i = 0; i < size; ++i)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
}

void buildMatchTable(vector<int> &T, char *a, int n)
{
    T.resize(n, 0);
    T[0] = -1;
    T[1] = 0;
    int k = 0;
    int i = 2;
    while(i < n)
    {
        if(a[i - 1] == a[k])
        {
            ++k, T[i] = k, ++i;
        } else if(k > 0)
        {
            k = T[k];
        } else
        {
            T[i] = 0;
            ++i;
        }
    }
}

void KMP(char *a, char *b, int n, int m, vector<int> &T, vector<int> &matches)
{
    int s = 0;//start of possible match
    int p = 0;//number of chars matching so far
    while( s + p < m )
    {
        if(b[s + p] == a[p])
        {
            if(p == n - 1)
            {
                matches.push_back(s);
                s += p - T[p];
                p = (T[p] != -1) ? T[p] : 0;
            } else
            {
                ++p;
            }
        } else
        {
            s += p - T[p];
            if(T[p] != -1)
            {
                p = T[p];
            } else
            {
                p = 0;
            }
        }
    }
}

void printSolution(vector<int> &matches)
{
    cout << matches.size() << endl;
    int n = (matches.size() < 1000) ? matches.size() : 1000;
    for(int i = 0; i < n; ++i)
    {
        cout << matches[i] << " ";
    }
    cout << endl;
}

void solve()
{
    char *a = (char*) calloc(2000000, sizeof(char));
    char *b = (char*) calloc(2000000, sizeof(char));
    scanf("%s %s", a, b);
    int n = strlen(a);
    int m = strlen(b);
    vector<int> T;
    vector<int> matches;
    buildMatchTable(T, a, n);
    KMP(a, b, n, m, T, matches);
    printSolution(matches);
}

int main(int argc, char *argv[])
{
    if(argc == 2)
    {
        redirectInput(argv[1],"strmatch.out");
    } else
    {
        redirectInput("strmatch.in","strmatch.out");
    }

    solve();

    return 0;
}