Cod sursa(job #1760358)

Utilizator borcanirobertBorcani Robert borcanirobert Data 20 septembrie 2016 18:33:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 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 + 1, MAXL);
    fin.getline(b + 1, MAXL);

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

void KMP()
{
    int q = 0, i;

    Prefix();

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

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

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

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

void Prefix()
{
    int q = 0, i;

    for ( i = 2; i <= N; i++ )
    {
        while ( q > 0 && 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] << ' ';
}