Cod sursa(job #2139646)

Utilizator Y0da1NUME JMECHER Y0da1 Data 22 februarie 2018 18:01:06
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

#define maxn 2000002

using namespace std;

string S, P, str;
int Z[2*maxn];
vector<int> aparitii;

void build_Z_array()
{
    int L, R;
    L = R = 0;
    for (int i = 1; i < str.size(); ++i)
    {
        if(i > R)
        {
            L = R = i;
            while(R < str.size() && str[R - L] == str[R])
                ++R;
            Z[i] = R - L;
            --R;
        }
        else
        {
            int k = i - L;
            if(Z[k] < R - i +1)
                Z[i] = Z[k];
            else
            {
                while(R < str.size() && str[R - L] == str[R])
                ++R;
            Z[i] = R - L;
            --R;
            }

        }
    }
}
int main()
{
    ifstream in ("strmatch.in");
    ofstream out ("strmatch.out");
    //necesar pt a testa codul cu problema de pe infoarena
    in>>P>>S;
    str = P;
    str+='$';
    str+=S;
    build_Z_array();
    for(int i = P.size() + 1; i < str.size(); ++i)
        if(Z[i] == P.size())
    {
        //cout<<"Potrivire la: "<<i - P.size() - 1<<"\n";
        aparitii.push_back(i - P.size() - 1);
    }
    int maxim = ((aparitii.size() > 1000) ? 1000 : aparitii.size());
    out<<aparitii.size()<<"\n";
    for(int i = 0; i < maxim; ++i)
        out<<aparitii[i]<<" ";


}