Cod sursa(job #1997592)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 4 iulie 2017 22:09:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <list>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char N[2000003],M[2000003];
int n,m,P[2000003];

int nrpoz;
list<int>poz;

void Prefix()
{
    int i,j;

    for( i = 0 , j = 1 ; j < n ; j++ )
    {
        while( i > 0 && N[i] != N[j] )
           i = P[i-1];
        if( N[i] == N[j] )
              i++;
        P[j] = i;
    }
}

void KMP()
{
    int i,j;
    for( i = 0 , j = 0 ; j < m ; j++ )
    {
        while( i > 0 && N[i] != M[j] )
            i = P[i-1];
        if( N[i] == M[j] )
              i++;
        if( i == n )
            if( ++nrpoz < 1001 )
                poz.push_back(j-n+1);
    }
}

int main()
{
    f>>N>>M;
    n = strlen(N);
    m = strlen(M);

    Prefix();
    KMP();

    g<<nrpoz<<'\n';
    for(list<int>::iterator it = poz.begin() ; it != poz.end() ; it++)
        g<<*it<<' ';

    return 0;
}