Cod sursa(job #2289361)

Utilizator dacianouaPapadia Mortala dacianoua Data 24 noiembrie 2018 14:25:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <cstring>
#define nmax 2000005
using namespace std;
FILE *fin,*fout;
char a[nmax], b[nmax];
int lps[nmax], n , m, nr, poz[1005];
void preprocess_lps()
{
    int i=0, j=-1;
    lps[0]=-1;
    while(i<m)
    {
        while(j>=0 && a[i]!=a[j])
            j=lps[j];
        i++;
        j++;
        lps[i]=j;
    }
}
int main()
{
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    fscanf(fin,"%s\n%s", a, b);
    m=strlen(a);
    n=strlen(b);
    preprocess_lps();
    int i=0, j=0;
    while(i<n)
    {
        while(j>=0 && b[i]!=a[j])
            j=lps[j];
        i++;
        j++;
        if(j==m)
        {
            j=lps[j];
            nr++;
            if(nr<=1000)
                poz[nr]=i-m;
        }
    }
    fprintf(fout,"%d\n", nr);
    if(nr>1000)
        nr=1000;
    for(int i=1;i<=nr;i++)
        fprintf(fout,"%d ", poz[i]);
    return 0;

}