Cod sursa(job #2290245)

Utilizator StefanZamfirStefan Zamfir StefanZamfir Data 26 noiembrie 2018 09:05:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

string txt, pat;
int z;
vector <int> plm;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin >> pat >> txt;
    int M = pat.size();
    int N = txt.size();
    int lps[M];
    //calculam lps
    int len = 0;
    lps[0]=0; // nu pot fi litere repetate pe prima poz
    int i = 1;
    while(i<M)
    {
        if(pat[i]==pat[len])
        {
            //daca avem 2 elm la fel
            ++len;
            lps[i]=len;
            //ne intoarncem direct la len
            ++i;
        }
        else
        {
            if(len!=0)
            {
                len = lps[len-1];
            }
            else
            {
                lps[i] = 0;
                ++i;
            }
        }
    }
    //cautare
    int _i = 0; //index pentru txt
    int _j = 0; // index pentru pat
    while(_i<N)
    {
        if(pat[_j]==txt[_i])
        {
            ++_i;
            ++_j;
        }
        if(_j==M)
        {
            ++z;
            if(z<=1000)
                plm.push_back(_i-_j);
            _j = lps[_j-1]; // ne intoarcem
        }
        //daca nu a fost gasit
        else if(_i<N && pat[_j]!=txt[_i])
        {
            if(_j!=0)
                _j=lps[_j-1];
            else ++_i;
        }
    }
    cout << z << '\n';
    for_each(plm.begin(),plm.end(),[](int a){
             cout << a << ' ';
             });
    return 0;
}