Cod sursa(job #1944085)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 28 martie 2017 22:30:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000002], b[2000002];
int i,q,lung[2000002],vs[1005],sol,n,m;
int main() {
    f>>a+1>>b+1;
    n=strlen(a+1), m=strlen(b+1);
    for (i=2; i<=n; i++) {
        while (a[q+1]!=a[i] && q)
            q=lung[q];
        if (a[q+1]==a[i]) q++;
        lung[i]=q;
    }
    for (i=1, q=0; i<=m; i++) {
        while (a[q+1]!=b[i] && q)
            q=lung[q];
        if (a[q+1]==b[i]) q++;
        if (q==n) {sol++;
            if (sol<=1000)
                vs[sol]=i-q;
            q=lung[q];
        }
    }
    g<<sol<<'\n';
    for (i=1; i<=sol; i++)
        g<<vs[i]<<' ';
}