Cod sursa(job #2473417)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 13 octombrie 2019 15:59:02
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb

#include <bits/stdc++.h>

using namespace std;

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

string a, b, c;
int z[5000000], r, l, k, p, n1, n2, n3;
vector <int> ans;

int main()
{
    fin >> a;
    fin >> b;

    c = a+b;
    n1 = a.size();
    n2 = b.size();
    n3 = c.size();
    for(int i = 1; i < n3; i++)
    {
        if(r < i)
        {
            k = i;
            p = 0;
            while(c[k] == c[p]) r = k, k++, p++, z[i]++;
            if(r >= i) l = i;
        }
        else
        {
            p = i-l;
            if(z[p] < r-i+1)
                z[i] = z[p];
            else
            {
                z[i] = r-i+1;
                k = r+1;
                p = z[p];
                l = i;
                while(c[p] == c[k])r = k, k++, p++, z[i]++;

            }


        }

    }
    for(int i = n1; i < n3; i++)
        if(z[i] >= n1) ans.push_back(i-n1);
    fout << ans.size() << '\n';
    int n = ans.size();
    for(int i = 0; i < n && i < 1000; i++)
        fout << ans[i] << " ";
    return 0;
}