Cod sursa(job #1997405)

Utilizator catalinlupCatalin Lupau catalinlup Data 4 iulie 2017 11:44:05
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define NMAX 1000
#define LMAX 2000000

using namespace std;

void PrefixTable(char pattern[],int Pi[]){
    int m=strlen(pattern);
    int k=0;
    Pi[0]=0;
    for(int i=1;i<m;i++){
        while(k>0&&pattern[i]!=pattern[k])
            k=Pi[k-1];
        if(pattern[k]==pattern[i])
            k++;
        Pi[i]=k;
    }
}

void KMP(char pattern[],char text[],int Pi[],int&num,int Rasp[]){
    int m=strlen(pattern);
    int n=strlen(text);
    int k=0;
    num=0;
    for(int i=0;i<n;i++){
        while(pattern[k]!=text[i]&&k>0)
            k=Pi[k];
        if(pattern[k]==text[i])
        {
            k++;
        }
        if(k==m){
            Rasp[++num]=i-k+1;
            k=Pi[k-1];
        }
    }
}
char patt[LMAX+2];
char text[LMAX+2];
ifstream in(INFILE);
ofstream out(OUTFILE);
int Pi[LMAX+2];
int Rasp[NMAX+2];
int NUM;
int main()
{

    in.getline(patt,LMAX+1);
    in.getline(text,LMAX+1);
    PrefixTable(patt,Pi);
    KMP(patt,text,Pi,NUM,Rasp);
    if(NUM>NMAX)
        NUM=NMAX;
    out<<NUM<<"\n";
    for(int i=1;i<=NUM;i++){
        out<<Rasp[i]<<" ";
    }
    return 0;
}