Cod sursa(job #1969140)

Utilizator borcanirobertBorcani Robert borcanirobert Data 18 aprilie 2017 12:04:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

string a, b;
int cnt;
vector<int> p, pos;
int N, M;

void Prefix( string& a );
void KMP();

int main()
{
    fin >> a >> b;
    N = a.size(), M = b.size();
    p = vector<int>(N);

    KMP();
    fout << cnt << '\n';
    for ( const int& x : pos )
        fout << x << ' ';

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

void Prefix( string& a )
{
    int q{0};
    for ( size_t i = 1; i < N; ++i )
    {
        while ( q > 0 && a[q] != a[i] )
            q = p[q];
        if ( a[q] == a[i] )
            ++q;
        p[i] = q;
    }
}

void KMP()
{
    int q{0};
    Prefix(a);
    for ( size_t i = 0; i < M; ++i )
    {
        while ( q > 0 && a[q] != b[i] )
            q = p[q - 1];
        if ( a[q] == b[i] )
            ++q;

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

            if ( cnt <= 1000 )
                pos.push_back(i + 1 - a.size());
        }
    }
}