Cod sursa(job #2449196)

Utilizator StanCatalinStanCatalin StanCatalin Data 18 august 2019 16:27:30
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
/// Z
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int dim = 2000005;

string s1,s2;
vector <int> omg;
int l,r,z[dim];

int main()
{
    in >> s1 >> s2;
    if (s1.lenght() > s2.length())
    {
        out << "0";
        return 0;
    }
    s2 = s1 + "$" + s2;
    int l = 0,r = 0;
    int n = s2.length();
    for (int i=1; i<n; i++)
    {
        if (i > r)
        {
            l = i;
            r = i;
            while (r < n && s2[r] == s2[r-l])
            {
                r++;
            }
            z[i] = r-l;
            r--;
        }
        else
        {
            if (z[i-l] < r-i+1)
            {
                z[i] = z[i-l];
            }
            else
            {
                l = i;
                while (r < n && s2[r] == s2[r-l])
                {
                    r++;
                }
                z[i] = r-l;
                r--;
            }
        }
    }
    int cnt = 0;
    for (int i=0; i<n; i++)
    {
        if (z[i] == s1.length())
        {
            cnt++;
            omg.push_back(i);
        }
    }
    out << cnt << "\n";
    if (omg.size() <= 1000)
    {
        for (int i=0; i<omg.size(); i++)
        {
            out << omg[i] - s1.length() - 1 << " ";
        }
    }
    else
    {
        for (int i=0; i<1000; i++)
        {
            out << omg[i] - s1.length() - 1 << " ";
        }
    }
    return 0;
}