Cod sursa(job #1755889)

Utilizator cristian.caldareaCaldarea Cristian Daniel cristian.caldarea Data 11 septembrie 2016 13:13:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;

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

vector<int> ans, p;
int n, m;
string a, b;

void Prefix();
void KMP();

int main()
{
    getline(fin, a);
    getline(fin, b);

    Prefix();
    KMP();

    fout << ans.size() << '\n';

    for ( auto x : ans )
        fout << x << ' ';

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

void Prefix()
{
    int k = 0;
    n = a.size();
    p = vector<int>(n + 1);
    for ( int i = 1; i < n; ++i )
    {
        while ( k > 0 && a[k] != a[i] )
            k = p[k - 1];

        if ( a[i] == a[k] )
            k++;
        p[i] = k;
    }
}

void KMP()
{
    int k = 0;
    m = b.size();
    for (int i = 0; i < m; ++i)
    {
        while( k > 0 && b[i] != a[k] )
            k = p[k - 1];

        if ( b[i] == a[k] )
            ++k;

        if (k == n)
            ans.push_back(i - n + 1);
        if ( ans.size() == 1000 )
            return;
    }
}