Cod sursa(job #3041601)

Utilizator stefan05Vasilache Stefan stefan05 Data 31 martie 2023 19:46:03
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
///infoarena Potrivirea sirurilor
#include <fstream>
#include <cstring>
#include <vector>

#define NMAX 2000005

using namespace std;

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

int n, m;
char a[NMAX*2], b[NMAX];
int lps[NMAX*2]; int k;
vector<int> ans; LL counter;
int i, j;

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

    n = strlen(a);
    m = strlen(b);

    a[n] = '#';
    a[n+1] = 0;
    strcat(a, b);

    k = 0;
    for (i = 1; a[i]; ++i)
    {
        while (k > 0 && a[i] != a[k]) k = lps[k-1];
        if (a[i] == a[k]) k++;
        lps[i] = k;
    }

    for (i = 0; b[i]; ++i)
        if (lps[i+n+1] == n)
        {
            counter ++;
            if (counter < 1000)
                ans.push_back(i-n+1);
        }

    fout <<counter<<'\n';
    for (auto x: ans)
        fout <<x<<' ';
    fout <<'\n';
    fout.close();
    return 0;
}