Cod sursa(job #2675219)

Utilizator rARES_4Popa Rares rARES_4 Data 21 noiembrie 2020 11:24:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
char text[2000001],secv[2000001];
int cnt;
int lps[2000001];
int lungimeText,lungimeSecv;
vector<int>poz;
void formare_lps()
{
    int st = 0;

    for(int i = 1; i<lungimeSecv; i++)
    {
        if(secv[i] == secv[st])
        {
            lps[i] = st+1;
            st++;
        }
        else
        {
            if(st)
            {
                st = lps[st-1];
            }
            else
                lps[i] = 0;
        }
    }
}
void verificare_secv_in_text()
{
    int indice_in_secv = 0;
    int i = 0;
    while(i<lungimeText)
    {
        if(text[i] == secv[indice_in_secv])
        {
            indice_in_secv++;
            i++;
        }
        else
        {
            if(indice_in_secv)
                indice_in_secv = lps[indice_in_secv-1];
            else
                i++;
        }
        if(indice_in_secv == lungimeSecv)
        {
            poz.push_back(i-(indice_in_secv));
            indice_in_secv = lps[indice_in_secv-1];
        }
    }
}
int main()
{
    f >> secv>> text;
    lungimeSecv = strlen(secv);
    lungimeText = strlen(text);
    formare_lps();
    verificare_secv_in_text();
    int lungime_v = poz.size();
    g<<lungime_v<< '\n';
    for(int i = 0; i<min(lungime_v,1001); i++)
        g << poz[i]<< " ";
}