Cod sursa(job #1997165)

Utilizator catalinlupCatalin Lupau catalinlup Data 3 iulie 2017 15:45:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define LMAX 2000100
#define NMAX 1000

using namespace std;

void CrPrefTable(char pat[],int n,int P[]){
    P[0]=0;
    int border=0;
    for(int i=1;i<n;i++){
        while(border>0&&pat[i]!=pat[border])
            border=P[border-1];
        if(pat[i]==pat[border])
            border=border+1;
        else{
            P[i]=0;
            border=0;
        }
        P[i]=border;
    }
}
int Pi[2*LMAX];
char str[2*LMAX];
void KMP(char pat[],char text[],int Rasp[],int&num){

    int m=strlen(pat);
    int n=strlen(text);
    int Pi[m+n+1];
    char str[m+n+1];
    for(int i=0;i<m;i++)
        str[i]=pat[i];
    str[m]='$';
    for(int i=0;i<n;i++){
        str[m+i+1]=text[i];
    }
    CrPrefTable(str,m+n+1,Pi);
    num=0;
    for(int i=m+1;i<m+n+1;i++){
        if(Pi[i]==m){
            Rasp[num++]=i-2*m;
        }
    }
}

ifstream in(INFILE);
ofstream out(OUTFILE);

char Pattern[LMAX];
char Text[LMAX];
int Rasp[LMAX];
int num;

int main()
{
    in.getline(Pattern,LMAX);
    in.getline(Text,LMAX);
    KMP(Pattern,Text,Rasp,num);
    if(num>NMAX)
        num=NMAX;
    out<<num<<"\n";
    for(int i=0;i<num;i++){
        out<<Rasp[i]<<" ";
    }
    return 0;
}