Cod sursa(job #2193625)

Utilizator alexmihai21Mihai Alexandru alexmihai21 Data 10 aprilie 2018 19:23:46
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAX 2000050
int n,m,SOL[MAX];
char s[MAX], pat[MAX];

void read(){
    fin>>pat;
    fin>>s;
    n=strlen(s);
    m=strlen(pat);
}

void findLPS(char *pat,int m, int *lps){
    int l=0;
    int i=1;
    lps[0]=0;
    while(i<m){
    if(pat[i]==pat[l]){
        l++;
        lps[i]=l;
        i++;
    }
     else if(pat[i]!=pat[l]){
        if(l!=0)
            l=lps[l-1];
        else if(l==0){
         i++;
         lps[i]=0;
        }

     }
}
}

void KMP(char *pat, char *s,int m, int n){
   int *lps;
   lps=(int*)malloc(m*sizeof(int));
   findLPS(pat,m,lps);
   int i=0;
   int j=0;
   int k=0;
   while(i<n){
     if(pat[j]==s[i]){
        j++;
        i++;
     }
     else
     if(j!=0)
        j=lps[j-1];
        else
            i++;
    if(j==m){
        j=lps[j-1];
        SOL[++k]=i-j;

    }



   }
   fout<<k<<'\n';
   for(i=0;i<k;i++)
    fout<<SOL[i]<<" ";

}




int main()
{
 read();
 KMP(pat,s,m,n);
}