Cod sursa(job #1674752)

Utilizator cristinamateiCristina Matei cristinamatei Data 4 aprilie 2016 20:40:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 2000003;

int n, m, pref[N], rez[N], poz;
char  a[N], b[N], c;

void calculprefixe()
{
    int k = 0, i;
    pref[1] = 0;
    for ( i = 2; i <= m; i++ )
    {
        while( k > 0 && a[k+1] != a[i] )
            k = pref[k];
        if (a[k+1] == a[i]) //if ( k != 0 )
            k++;
        pref[i] = k;
    }
}

void kmp()
{
    int k = 0, i;
    for ( i = 1; i <= n; i++ )
    {
        while( k > 0 && a[k+1] != b[i] )
            k = pref[k];
        if ( a[k+1] == b[i] ) //if ( k != 0 )
            k++;
        if ( k == m ) /// am potrivire la poz i-m
        {
            poz++;
            rez[poz] = i-m;
        }
    }
}

int main()
{
    in.get(c);
    while( c != '\n' && c != NULL )
    {
        m++;
        a[m] = c;
        in.get(c);
    }
    in.get(c);
    while( c != '\n' && c != NULL )
    {
        n++;
        b[n] = c;
        in.get(c);
    }
    calculprefixe();
    kmp();
    out << poz<<'\n';
    if ( poz > 1000 )
        poz = 1000;
    for ( int i = 1; i <= poz; i++ )
        out << rez[i]<<' ';
    return 0;
}