Cod sursa(job #305237)

Utilizator cosserBula Ionut cosser Data 16 aprilie 2009 18:51:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<iostream>
#include<fstream>
#include<string.h>

using namespace std;

#define mini(a,b) ((a<b) ? a:b)
#define IMAX 2000001

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

int n,m,i,sir[IMAX],nrap,ap[1001];
char a[IMAX],b[IMAX];

void functie()
{
    int k;

    sir[0]=-1;
  //  sir[-1]=-1;
    k=-1;
    for(i=1;i<m;i++)
       {
           while( k>-1 && a[k+1]!=a[i] )
                                             k=sir[k];
           if(a[k+1]==a[i])
                                k++;
            sir[i]=k;
       }

}


void kmp()
{
    int j;
    n=strlen(b);
    m=strlen(a);
    functie();
    j=-1;
    for(i=0;i<n;i++)
        {
            while(j>-1 && a[j+1]!=b[i])
                                    j=sir[j];
            if(a[j+1]==b[i])
                                        j++;
            if(j==m-1)
                {
                   // o<<"\n Modelul apare cu deplasamentul "<<i-m+1;
                    j=sir[j];
                    nrap++;
                    if(nrap<=1000)
                            ap[nrap]=i-m+1;
                }
        }
}

int main()
{
int i;
f.get(a,IMAX);
f.get();
f.get(b,IMAX);

kmp();

o<<nrap<<"\n";
for(i=1;i<=mini(nrap,1000);i++)
    o<<ap[i]<<" ";




return 0;}