Cod sursa(job #2807234)

Utilizator SoulSnorterPetre Robert Cristian SoulSnorter Data 23 noiembrie 2021 16:36:51
Problema Potrivirea sirurilor Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
//#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

int cnt = 0, m;

string harta, sir;

vector<int> z;
vector<int> rez;

vector<int> z_function(string s)
{
    int n = s.length();
    vector<int> z(n);
    int left = 0, right = 0;
    for(int i = 1; i < n; i++)
    {
        if (i <= right)
            z[i] = min (right - i + 1, z[i-left]);
        while (i + z[i] < n & s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > right)
        {
            left = i;
            right = i + z[i] - 1;
        }
    }
    return z;
}

int main()
{
    in>>sir;
    m = sir.size();
    in>>harta;
    sir += harta;
    z = z_function(sir);
    for(int i = 0; i < z.size(); i++)
    {
        if(z[i] == m)
        {
            cnt++;
            rez.push_back(i - m);
        }
    }
    out<<cnt<<"\n";
    for(int i = 0; i < rez.size(); i++)
    {
        out<<rez[i]<<" ";
    }
}