Cod sursa(job #3141904)

Utilizator gianiferSpita Alexandru-Mihai gianifer Data 17 iulie 2023 15:49:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000002], b[2000002];
char A[2000002], B[2000002];
int k = 0, sol[1001], p[2000001], l = 0;
int n, m;
int main()
{
    fin >> A >> B;
    strcpy(a + 1, A);
    strcpy(b + 1, B);
    p[1] = 0;
    n = strlen(a + 1);
    m = strlen(b + 1);
    for (int i = 2; i <= n; i++)
    {
        while (l != 0 && a[i] != a[l + 1])
            l = p[l];
        if (a[i] == a[l + 1])
            l++;
        p[i] = l;
    }
    l = 0;
    for (int i = 1; i <= m; i++)
    {
        while (l != 0 && b[i] != a[l + 1])
            l = p[l];

        if (b[i] == a[l + 1])
            l++;
        if (l == n)
        {k++;
            if (k <=1000)
                sol[k] = i - n;
            l = p[l];
        }
    }
    if(k>1000)
    k=1000;
    fout << k << '\n';
    for (int i = 1; i <= k; i++)
        fout << sol[i] << " ";
}