Cod sursa(job #2800804)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 13 noiembrie 2021 23:44:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>

using namespace std;

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

string a, b, s;
long long pi[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 + 2;
    if(a_len > b_len)
    {
        fout << 0;
        return 0;
    }
    k = 0;
    for(int i = 2; i < s_len; i++)
    {
        while(k != 0 && s[i] != s[k + 1])
            k = pi[k];
        if(s[i] == s[k + 1])
            k++;
        pi[i] = k;
        if(pi[i] == a_len)
        {
            afis++;
            if(afis <= 1000)
                ans[afis] = i - 1 - 2 * a_len;
        }
    }
    fout << afis << '\n';
    afis = min(afis, 1LL*1000);
    for(int i = 1; i <= afis; i++)
        fout << ans[i] << ' ';
    return 0;
}