Cod sursa(job #2466079)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 1 octombrie 2019 13:46:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <cstring>
#include <vector>

#define MAX 2000005
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char X[MAX], Y[MAX];
int P[MAX];
vector<int> v;

void make_prefix(){
    int lg = strlen(X);
    --lg;
    int k = 0;
    for(int i = 2; i <= lg; ++i){
        while(k > 0 && X[k + 1] != X[i])
            k = P[k];
        if(X[k + 1] == X[i])
            ++k;
        P[i] = k;
    }
}

void kmp(){
    int lg = strlen(Y) - 1;
    int lg2 = strlen(X) - 1;
    int k = 0;
    for(int i = 1; i <= lg; ++i){
        while(k > 0 && X[k + 1] != Y[i])
            k = P[k];
        if(X[k + 1] == Y[i])
            ++k;
        if(k == lg2){
            if(v.size() < 1000)
                v.push_back(i - lg2);
            else return;
        }
    }
}

int main()
{
    fin >> X >> Y;
    int lg1 = strlen(X);
    int lg2 = strlen(Y);
    for(int i = lg1 - 1; i >= 0; --i)
        X[i + 1] = X[i];
    for(int i = lg2 - 1; i >= 0; --i)
        Y[i + 1] = Y[i];

    make_prefix();
    kmp();

    fout << v.size() << '\n';
    for(int i = 0; i < v.size(); ++i)
        fout << v[i] << ' ';
    fout << '\n';
    return 0;
}