Cod sursa(job #2473407)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 13 octombrie 2019 15:48:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 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(i <= r)
           z[i] = min(z[i-l], r-i+1);
        while(i+z[i] < n3 && c[z[i]] == c[z[i]+i]) z[i]++;

        if(r < z[i]+i-1)
        {
            r = z[i]+i-1;
            l = 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++)
        fout << ans[i] << " ";
    return 0;
}