Cod sursa(job #2351556)

Utilizator borcanirobertBorcani Robert borcanirobert Data 22 februarie 2019 15:24:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
/// Se dau doua siruri A si B formate din litere mici si mari ale alfabetului englez si din cifre.
/// Se cere gasirea tuturor aparitiilor sirului A ca subsecventa a sirului B.
#include <fstream>
#include <cstring>
using namespace std;

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

const int MAXL = 2000005;
const int MAXO = 1005;
int N, M;
char a[MAXL], b[MAXL];
int nr, rez[MAXO];
int p[MAXL];

void Read();
void KMP();
void Prefix();
void Write();

int main()
{
    Read();
    KMP();
    Write();

    fin.close();
    fout.close();
    return 0;
}


void Read()
{
    fin.getline(a, MAXL);
    fin.getline(b, MAXL);

    N = strlen(a);
    M = strlen(b);
}

void KMP()
{
    int q = -1, i;

    Prefix();

    for ( i = 0; i < M; i++ )
    {
        while ( q != -1 && a[q + 1] != b[i] )
            q = p[q];

        if ( a[q + 1] == b[i] )
            ++q;

        if ( q == N - 1 )
        {
            q = p[N - 1];

            ++nr;
            if ( nr <= 1000 )
                rez[nr] = i - N + 1;
        }
    }
}

void Prefix()
{
    int q = -1, i;

    p[0] = -1;
    for ( i = 1; i < N; i++ )
    {
        while ( q != -1 && a[q + 1] != a[i] )
            q = p[q];
        if ( a[q + 1] == a[i] )
            ++q;

        p[i] = q;
    }
}

void Write()
{
    fout << nr << '\n';
    for ( int i = 1; i <= min( 1000, nr ); i++ )
        fout << rez[i] << ' ';
}