Cod sursa(job #2433850)

Utilizator ViAlexVisan Alexandru ViAlex Data 29 iunie 2019 14:45:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include<iostream>
#include<string>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void compute_lsp(int*lsp_array,string to_compute)
{
    int i=1,l=0;
    lsp_array[0]=0;
    while(i<to_compute.length())
    {
        if(to_compute[i]==to_compute[l])
        {

            l++;
            lsp_array[i]=l;
            i++;
        }
        else
        {
            if(l!=0)
            {
                l=lsp_array[l-1];
            }
            else
            {
                lsp_array[i]=0;
                i++;
            }
        }
    }

}


vector<int> kmp(string main,string pattern)
{
    vector<int> to_return;
    int lsp[pattern.length()];
    compute_lsp(lsp,pattern);
    int i=0,p=0;
    while(i<main.length())
    {
        if(main[i]==pattern[p])
        {
            i++;
            p++;
        }
        if(p==pattern.length())
        {
            to_return.push_back(i-p);
            p=lsp[p-1];
        }
        if(i<main.length() &&main[i]!=pattern[p])
        {
            if(p!=0)
            {
                p=lsp[p-1];
            }
            else
                i++;
        }

    }
    return to_return;



}

int main()
{
    string a,b;
    in>>a>>b;
    vector<int> results=kmp(b,a);
    out<<results.size()<<'\n';
    for(int i=0; i<results.size(); i++)
        out<<results[i]<<' ';
    return 0;
}