Cod sursa(job #2443725)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 29 iulie 2019 12:27:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int LMax = 2e6;

int N, M, K, Sol[1005], Match[LMax + 5];
char A[LMax + 5], B[LMax + 5];

void Make_Prefix()
{
    int q = 0;

    for(int i = 2; i <= N; i++)
    {
        while(q && A[q + 1] != A[i])
            q = Match[q];

        if(A[q + 1] == A[i])
            q++;

        Match[i] = q;
    }
}

int main()
{
    fin >> A + 1 >> B + 1;

    N = strlen(A + 1);
    M = strlen(B + 1);
    Make_Prefix();

    int q = 0;

    for(int i = 1; i <= M; i++)
    {
        while(q && A[q + 1] != B[i])
            q = Match[q];

        if(A[q + 1] == B[i])
            q++;

        if(q == N)
        {
            q = Match[q];///nu exista A[N + 1]

            if(++K <= 1000)
                Sol[K] = i;
        }
    }
    fout << K << '\n';

    for(int i = 1; i <= K; i++)
        fout << Sol[i] - N << " ";

    fin.close();
    fout.close();

    return 0;
}