Cod sursa(job #1771018)

Utilizator NicuBaciuNicu Baciu NicuBaciu Data 5 octombrie 2016 09:43:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector<int> prefix_function (string Z) {

    int n = (int) Z.length();

    vector<int> F (n);

     F[0]=0;

    for (int i=1; i<n; ++i) {

        int j = F[i-1];

        while (j > 0 && Z[i] != Z[j])

            j = F[j-1];

        if (Z[i] == Z[j])  ++j;

        F[i] = j;

    }

    return F;

}

vector <int> poz;

int main()
{
    string p, t;

    string a;

    fin >> p >> t;

    a=p+"#"+t;

    vector<int> b(a.size());
    b = prefix_function(a);

    int ct = 0;
    for(int i=0; i<b.size(); i++)
    {
        if(b[i]==p.size())
        {
            ct++;
            poz.push_back(i-2*p.size());
        }
    }

    fout << ct << '\n';

    for(int i=0; i<ct; i++){
        fout << poz[i] << ' ';
    }

    return 0;
}