Cod sursa(job #259993)

Utilizator catalina5catalina serban catalina5 Data 16 februarie 2009 12:07:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#define MAX 2000020

using namespace std;

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

char s1[MAX],s2[MAX];
int lg1,lg2,v[MAX];
int nr,rez[1005];

void preg()
{
     v[1]=0;
     int k=0;
     for (int i=2;i<=lg2;i++)
     {
          while (k && s2[k+1]!=s2[i])
               k=v[k];
          if (s2[k+1]==s2[i])
               k++;
          v[i]=k;
     }
}

void kmp()
{
     int k=0;
     for (int i=1;i<=lg1;i++)
     {
          while (k && s2[k+1]!=s1[i])
               k=v[k];
          if (s2[k+1]==s1[i])
               k++;
          if (k==lg2)
          {
               nr++;
               if (nr<=1000)
                    rez[nr]=i-lg2;
               k=v[k];
          }
     }
}

void afisare()
{
     fout<<nr<<"\n";
     if (nr>1000)
          nr=1000;
     for (int i=1;i<=nr;i++)
          fout<<rez[i]<<" ";
}

void act(char sir[MAX],int &n)
{
     if (sir[strlen(sir)-1]=='\n')
          sir[strlen(sir-1)]=0;
     n=strlen(sir);
     for (int i=n;i>0;i--)
          sir[i]=sir[i-1];
     sir[0]='\0';
}

void citire()
{
     fin.getline(s2,MAX);
     fin.getline(s1,MAX);
     act(s1,lg1);
     act(s2,lg2);
}

int main ()
{
     citire();
     preg();
     kmp();
     afisare();
     return 0;
}