Cod sursa(job #2800816)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 14 noiembrie 2021 00:25:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>

using namespace std;

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

string a, b, s;
long long z[4000005], k, afis, ans[1005], a_len, b_len, s_len;

int main()
{
    fin >> a >> b;
    s = a + '$' + b;
    a_len = a.size();
    b_len = b.size();
    s_len = a_len + b_len + 1;
    if(a_len > b_len)
    {
        fout << 0;
        return 0;
    }
    int st = 0, dr = 0, k;
    for(int i = 1; i < s_len; i++)
    {
        if(i > dr)
        {
            st = i;
            dr = i;
            while(dr < s_len && s[dr - st] == s[dr])
                dr++;
            z[i] = dr - st;
            dr--;
        }
        else
        {
            k = i - st;
            if(z[k] < dr - i + 1)
                z[i] = z[k];
            else
            {
                st = i;
                while(dr < s_len && s[dr - st] == s[dr])
                    dr++;
                z[i] = dr - st;
                dr--;
            }
        }
        if(z[i] == a_len)
        {
            afis++;
            if(afis <= 1000)
                ans[afis] = i - 1 - a_len;
        }
    }
    fout << afis << '\n';
    afis = min(afis, 1LL*1000);
    for(int i = 1; i <= afis; i++)
        fout << ans[i] << ' ';
    return 0;
}