Cod sursa(job #2444314)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 31 iulie 2019 09:52:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstring>
#include <fstream>

using namespace std;

ifstream i("strmatch.in");
ofstream o("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()
{
    i >> 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;
        }
    }
    o << K << '\n';
    K = min(K, 1000);

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

    return 0;
}