Cod sursa(job #470276)

Utilizator APOCALYPTODragos APOCALYPTO Data 12 iulie 2010 17:56:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>
char a[2000003],p[2000003];
int N,M,pi[2000003],nah;
vector<int> q;
ofstream fout("strmatch.out");
void cit()
{
    ifstream fin("strmatch.in");
    fin.getline(p,2000003);
    fin.getline(a,2000003);

    N=strlen(a);
    M=strlen(p);
     int i;
     for(i=N;i>=0;i--) a[i+1]=a[i];
     for(i=M;i>=0;i--) p[i+1]=p[i];

    fin.close();

}

void calc_pi()
{int i,k;
  k=0;
  pi[1]=0;
  cout<<"\n";

    for(i=2;i<=M;++i )
    {
        while(k>0&&p[k+1]!=p[i])
        {
            k=pi[k];
        }

        if(p[k+1]==p[i])
          k++;
        pi[i]=k;

    }


}
void kmp()
{int nah=0;
    int i,k=0;
    calc_pi();
    cout<<"\n";
    for(i=1;i<=N;++i)
     {
     while(k>0 && p[k+1]!=a[i])
     {
         k=pi[k];
     }
     if(p[k+1]==a[i])
        k++;
     if(k==M)
     {   nah++;
         q.push_back(i-M);
         k=pi[k];

     }


     }
     fout<<nah<<"\n";
     if(nah)
     {
         for(i=0;i<=nah-1&&i<=999;i++)
           fout<<q[i]<<" ";
     }
     fout<<"\n";
}
int main()
{
    cit();
    kmp();
    fout.close();
    return 0;
}