Cod sursa(job #1779685)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 15 octombrie 2016 15:57:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <string>
#include <fstream>
#include <vector>

using namespace std;

string 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(){
    ifstream fin ("strmatch.in");
    fin >> a >> b;
    fin.close();
}

void prefix_table(){
    int j(0);
    for (unsigned i = 1; i < a.size(); ++i){
        while (j && a[j] != a[i])
            j = p[j-1];
        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(){
    ofstream fout ("strmatch.out");
    fout << s.size() << "\n";
    unsigned t = min(s.size(), 1000);
    for (unsigned i = 0; i < t; ++i)
        fout << s[i] << " ";
    fout.close();
}