Cod sursa(job #1941242)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 27 martie 2017 08:42:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <iostream>

using namespace std;
int a[2000001],b[2000001],p[2000001],inc[1001];
void calcp (int n){
    int l,i;
    l=0;
    for (i=2;i<=n;i++){
        while (l>0 && a[l+1]!=a[i])
            l=p[l];
        if (a[i]==a[l+1])
            l++;
        p[i]=l;
    }
}
int main()
{
    FILE *fin=fopen ("strmatch.in","r");
    FILE *fout=fopen ("strmatch.out","w");
    int n,m,i,l,sol;
    char c;
    c=fgetc (fin);
    n=m=0;
    while (c!='\n'){
        a[++n]=c;
        c=fgetc (fin);
    }
    c=fgetc (fin);
    while (c!='\n' && c!=EOF){
        b[++m]=c;
        c=fgetc (fin);
    }
    calcp (n);
    l=0;
    sol=0;
    for (i=1;i<=m;i++){
        while (l>0 && b[i]!=a[l+1])
            l=p[l];
        if (b[i]==a[l+1])
            l++;
        if (l==n){
            sol++;
            if (sol<=1000)
                inc[sol]=i-l;
            l=p[l];
        }
    }
    fprintf (fout,"%d\n",sol);
    for (i=1;i<=min(sol,1000);i++)
        fprintf (fout,"%d ",inc[i]);
    return 0;
}