Cod sursa(job #2366166)

Utilizator victorv88Veltan Victor victorv88 Data 4 martie 2019 18:49:16
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

int vector_ajutator[2000005], l;

char pattern[2000005], sir_mare[2000005];

vector<int>rasp;

void creeare_vector_ajutator()
{
    int i=0, j=1;
    vector_ajutator[0]=0;
    while (j<l)
    {
        if (pattern[i]==pattern[j])
        {
            vector_ajutator[j]=i+1;
            ++i;
            ++j;
        }
        else
        {
            if (i==0)
               {
                   vector_ajutator[j]=0;
                    ++j;
               }
            else
            {
                i=vector_ajutator[i-1];
            }
        }
    }
}

void comparare()
{
    int l_mare=strlen(sir_mare);
    int ind_sir=0, ind_pattern=0;
    while (ind_sir<l_mare)
    {
        if (sir_mare[ind_sir]==pattern[ind_pattern])
        {
            ++ind_pattern;
            if (ind_pattern==l)
            {
                rasp.push_back(ind_sir-l+1);
                ind_pattern=vector_ajutator[ind_pattern-1];
            }
        }
        else
        {
            if (ind_pattern==0)
                ind_pattern=0;
            else{
            ind_pattern=vector_ajutator[ind_pattern-1];
            }
        }
        ++ind_sir;
    }
    g << rasp.size() << '\n';
    for (auto &v:rasp)
    {
        g << v <<' ';
    }
}

int main()
{
    f >> pattern;
    l=strlen(pattern);
    creeare_vector_ajutator();
    f >> sir_mare;
    comparare();
    return 0;
}