Cod sursa(job #1779575)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 15 octombrie 2016 14:08:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <vector>

using namespace std;

vector<char> a, b;
vector<int> s;
int p[2000005];

void read();
void prefix_table();
void kmp();
unsigned min(unsigned, unsigned);
void write();

int main()
{
    read();
    prefix_table();
    kmp();
    write();
    return 0;
}

void read(){
    freopen("strmatch.in", "r", stdin);
    char q;
    do{
        scanf("%c", &q);
        a.push_back(q);
    }while(q != '\n');
    do{
        scanf("%c", &q);
        b.push_back(q);
    }while(q != '\n');
    a.pop_back();
    b.pop_back();
    fclose(stdin);
}

void prefix_table(){
    int j(0);
    for (unsigned i = 1; i < a.size(); ++i){
        while (j && a[j] != a[i])
            j = p[j];
        if (a[j] == a[i])
            ++j;
        p[i] = j;
    }
}

void kmp(){
    unsigned j(0);
    for (unsigned i = 0; i < b.size(); ++i){
        while(j && a[j] != b[i])
            j = p[j-1];
        if (a[j] == b[i])
            ++j;
        if (j == a.size())
            s.push_back(i - a.size() + 1);
    }
}

unsigned min(unsigned x, unsigned y){
    if (x < y)
        return x;
    return y;
}

void write(){
    freopen ("strmatch.out", "w", stdout);
    printf ("%d\n", s.size());
    unsigned t = min(s.size(), 1000);
    for (unsigned i = 0; i < t; ++i)
        printf ("%d ", s[i]);
    fclose(stdout);
}