Cod sursa(job #2027400)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 26 septembrie 2017 01:06:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define MAX 2000005
#define NMAX 1000
using namespace std;

string a, b;
int nr, p[MAX];
vector<int> apps;

void prefix() {
    p[0] = -1;
    int k = -1;
    for(int i = 1; i < a.size(); ++i) {
        if(a[i] == a[k + 1])
            ++k;
        else
            while(k >= 0 && a[i] != a[k + 1])
                k = p[k];
        p[i] = k;
    }
}

void kmp() {
    prefix();
    int k = -1;
    for(int i = 0; i < b.size(); ++i) {
        while(k >= 0 && a[k + 1] != b[i])
            k = p[k];
        if(a[k + 1] == b[i])
            ++k;
        if(k == a.size() - 1) {
            ++nr;
            if(nr <= NMAX)
                apps.push_back(i - a.size() + 1);
        }
    }
}

int main() {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    getline(f, a);
    getline(f, b);

    kmp();

    g << nr << "\n";
    for(int i = 0; i < apps.size(); ++i)
        g << apps[i] << " ";
    return 0;
}