Cod sursa(job #2180173)

Utilizator Narvik13Razvan Roatis Narvik13 Data 20 martie 2018 17:52:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define MAX_SIR 2000002

using namespace std;

ifstream f("strmatch.in");
ofstream o("strmatch.out");

int prefix[MAX_SIR], total;
string cuv, sir;
vector <int> res;

void make_prefix()
{
    int l = cuv.size(), j = 0;

    for(int i = 1; i < l; ++i)
    {
        while(j > 0 && cuv[i] != cuv[j])
            j = prefix[j-1];

        if(cuv[i] == cuv[j])
            ++ j;

        prefix[i] = j;
    }
}

void make_kmp()
{
    int l = sir.size(), j = 0;

    for(int i = 0; i < l; ++i)
    {
        while(j > 0 && cuv[j] != sir[i])
            j = prefix[j-1];

        if(cuv[j] == sir[i])
            ++ j;

        if(j == cuv.size())
        {
            if(total < 1000)
            {
                res.push_back(i - j + 1);
            }

            total ++;
        }
    }
}


int main()
{
    f >> cuv >> sir;
    make_prefix();
    make_kmp();
    o << res.size() << '\n';
    for(auto i: res)
        o << i << ' ';
    return 0;
}