Cod sursa(job #1471929)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 15 august 2015 17:22:22
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <cstring>

#define MAXN 2000001
#define MAXM 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int Prefix[MAXM+3],sol[1001],nrsol;
char P[MAXM+1], T[MAXN+1];

void KMP_prefix(char P[],int Prefix[])
{
    int a,b,length;
    length=strlen(P);
    Prefix[0]=-1;
    Prefix[1]=0;
    a=0;
    for(b=2;b<=length;b++)
    {
        while(a>0 && P[a+1]!=P[b])
            a=Prefix[a];
        if(P[a+1]==P[b])
            a=a+1;
        Prefix[b]=a;
    }
}

void KMP(char T[],char P[], int Prefix[])
{
     int i,j,k,n,m;
     i=0;j=0;k=0;
     m=strlen(P) ;
     n=strlen(T) ;

     while(n-k+2 >= m)
     {
         while(j<m && T[i]==P[j])  { i++; j++; }

         if(j>=m)
            {
                nrsol++;
                sol[nrsol]=k-1;
            }
        if (nrsol>=1000)
            break;
        if(Prefix[j]>0)
            k=i-Prefix[j]+1;
         else
            {
                if(i==k)
                    i++;
                k=i;
            }
        if(j>0)
            j=Prefix[j]+1;
     }
}
int main()
{
    fin.getline(P,MAXM);
    fin.getline(T,MAXN);


    KMP_prefix(P,Prefix);
    KMP(T,P,Prefix);

    fout<<nrsol<<'\n';
    int i;
    for(i=1;i<=nrsol;i++)
        fout<<sol[i]<<' ';
    fout<<'\n';

        return 0;
}