Cod sursa(job #1755900)

Utilizator cristian.caldareaCaldarea Cristian Daniel cristian.caldarea Data 11 septembrie 2016 13:27:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 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, nr;
string a, b;

void Prefix();
void KMP();

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

    Prefix();
    KMP();
    nr = ans.size();
    fout << nr << '\n';

    for ( int i = 0; i < nr && i < 1000; i++)
        fout << ans[i] << ' ';

    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);

    }
}