Cod sursa(job #2288897)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 24 noiembrie 2018 09:04:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>
#define nmax 2000005

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n,m,k,p[nmax],nr,v[1005];
char a[nmax],c[nmax];

int main() {
    int i,j;
    f.getline(c+1,nmax);
    f.getline(a+1,nmax);
    n=strlen(c+1);
    m=strlen(a+1);
    for (i=2;i<=n;i++) {
        while (k!=0 && c[k+1]!=c[i]) k=p[k];
        if (c[k+1]==c[i]) k++;
        p[i]=k;
    }
    k=0;
    for (i=1;i<=m;i++) {
        while (k!=0 && c[k+1]!=a[i]) k=p[k];
        if (c[k+1]==a[i]) k++;
        if (k==n) {
            nr++;
            if (nr<=1000) v[nr]=i-n;
        }
    }
    g<<nr<<'\n';
    for (i=1;i<=min(nr,1000);i++) g<<v[i]<<' ';
    return 0;
}