Cod sursa(job #1036971)

Utilizator romykPrehari Romica romyk Data 19 noiembrie 2013 19:54:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include<stdio.h>
#include <string.h>
using namespace std;
int poz[10001],po=0;;
void preKmp( char* pattern , int pattern_length, int kmpNext[] )
{
    int i , j;
    i = 0;
    j = -1;
    kmpNext[ 0 ] = -1;
    while ( i < pattern_length )
    {
        while ( j > -1 && pattern[ i ] != pattern[ j ] )
            j = kmpNext[ j ];
        i++;
        j++;
        if ( pattern[ i ] == pattern[ j ] )
            kmpNext[ i ] = kmpNext[ j ];
        else
            kmpNext[ i ] = j;
    }
}

void knuth_morris_pratt( char* pattern , int pattern_length , char* source , int source_length )
{
    int i , j;
    int kmpNext[ 20000 ];
    preKmp( pattern , pattern_length , kmpNext );
    i = 0;
    j = 0;
    while ( j < source_length )
    {
        while ( i > -1 && pattern[ i ] != source[ j ] )
            i = kmpNext[ i ];
        i++;
        j++;
        if ( i >= pattern_length )
        {
            poz[po]= j - i;
            po++;
            i = kmpNext[ i ];
        }
    }
}

int main()
{

    char a[2000000],b[2000000];
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    cin.get(a,2000000);
    cin.get();
    cin.get(b,2000000);
    knuth_morris_pratt(a ,strlen(a) , b ,strlen(b));
    cout<<po<<endl;
    if(po>1000)
        po=1000;
    for(int i=0;i<po;i++)
    cout <<poz[i]<<" ";
    return 0;
}