Cod sursa(job #2662930)

Utilizator XeinIonel-Alexandru Culea Xein Data 24 octombrie 2020 20:52:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <string.h>
#include <vector>

using namespace std;

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    char A[2000000], ch;
    int N, A_index = -1, B_index = -1, CONTOR = 0;
    vector<int> prefix, SOL;

    f.getline(A, 2000001);
    N = strlen(A);

    prefix.push_back(-1);
    for(int i = 1; i < N; i++)
    {
        int aux = prefix.back() + 1;
        if(A[i] == A[aux])
            prefix.push_back(aux);
        else
            prefix.push_back(-1);
    }

    while(f >> ch)
    {
        B_index++;
        while(A_index > -1 && A[A_index + 1] != ch)
            A_index = prefix[A_index];
        if(A[A_index + 1] == ch)
            A_index++;
        if(A_index == N - 1)
        {
            if(CONTOR < 1000)
                SOL.push_back(B_index - N + 1);
            CONTOR++;
            A_index = prefix[A_index];
        }
    }

    g << CONTOR << '\n';
    if(CONTOR > 1000)
        CONTOR = 1000;
    for(int i = 0; i < CONTOR; i++)
        g << SOL[i] << ' ';
    return 0;
}