Cod sursa(job #305293)

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

#define IMAX 2000666

using namespace std;

ifstream f ("strmatch.in");
ofstream o ("strmatch.out");
char a[IMAX],b[IMAX];
int sir[IMAX],nrsol,sol[1001],m,n;

void functie()
{
    int k,i;
    k=-1;
    sir[0]=-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;
        }
}

int main()
{
f.get(a,IMAX);
f.get();
f.get(b,IMAX);
m=strlen(a);
n=strlen(b);

int i,j;
j=-1;
functie();
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)
               {
                    j=sir[j];
                   nrsol++;
                    if(nrsol<=1000)
                      sol[nrsol]=i-m+1;
                }

    }

o<<nrsol<<"\n";
if(nrsol>1000)
        nrsol=1000;

for(i=1;i<=nrsol;i++)
        o<<sol[i]<<" ";



return 0;}