Cod sursa(job #2800799)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 13 noiembrie 2021 23:28:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>

using namespace std;

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

string a, b, s;
int pi[4000005], k, afis, ans[1005];

int main()
{
    fin >> a >> b;
    s = '$' + a + '$' + b;
    k = 0;
    for(int i = 2; i < (int) s.size(); 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.size())
        {
            afis++;
            ans[afis] = i - 1 - 2 * a.size();
        }
    }
    fout << afis << '\n';
    for(int i = 1; i <= min(afis, 1000); i++)
        fout << ans[i] << ' ';
    return 0;
}