Cod sursa(job #2289359)

Utilizator dacianouaPapadia Mortala dacianoua Data 24 noiembrie 2018 14:18:51
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define nmax 2000005
using namespace std;
FILE *fin,*fout;
char txt[nmax],pat[nmax],lps[nmax];
int poz[1001],counter;
void Pattern_Preprocessing(const char* a)
{
    int a_length=strlen(a);
    lps[0]=0;
    int i=0,j=1;
    while(j<a_length)
        if(a[i]==a[j])
            i++,lps[j]=i,j++;
        else
        {
            if(i)
                i=lps[i-1];
            else
                lps[j]=0,j++;
        }
}
void KMP(const char *a, const char *b)
{
    int m=strlen(a),n=strlen(b);
    Pattern_Preprocessing(a);
    int i=0,j=0;
    while(i<n)
    {
        if(a[j]==b[i])
            i++,j++;
        if(j==m)
            poz[++counter]=i-j,j=lps[j-1];
        else if(i<n && a[j]!=b[i])
        {
            if(j)
                j=lps[j-1];
            else
                i++;
        }
    }
}
int main()
{
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    fscanf(fin,"%s%s",&pat,&txt);
    KMP(pat,txt);
    fprintf(fout,"%d\n",counter);
    for(int i=1;i<=counter;i++)
        fprintf(fout,"%d ",poz[i]);
    return 0;
}