Cod sursa(job #1989255)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 6 iunie 2017 17:39:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

vector<int> Z(string s, const string &pattern)
{
    vector<int> ret;
    vector<int> z;
    if(s.size() < pattern.size())
        return ret;
    s = pattern + s;
    z.resize(s.size());
    for(int i = 1; i < s.size() && s[i] == s[i-1]; ++i, ++z[1]);
    int dr;
    z[0] = -1;
    for(int i = 2; i < s.size(); ++i)
    {
        if(z[i-1] <= 1)
            dr = i;
        else
            dr = i + min(z[1], z[i-1]-1);
        while(dr < s.size() && s[dr] == s[dr-i])
            ++dr;
        z[i] = dr - i;
    }
    for(int i = pattern.size(); i < z.size(); ++i)
        if(z[i] >= pattern.size())
            ret.push_back(i - pattern.size());
    return ret;
}

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    string a, b;
    in >> a >> b;
    vector<int> sol = Z(b, a);
    out << sol.size() << "\n";
    for(int i = 0; i < sol.size() && i < 1000; ++i)
        out << sol[i] << " ";
    in.close();
    out.close();
    return 0;
}