Cod sursa(job #2073949)

Utilizator ioana_marinescuMarinescu Ioana ioana_marinescu Data 23 noiembrie 2017 21:18:40
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
const int NMAX = 2000005;
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[NMAX], s[NMAX];
int n, m, pi[NMAX], poz[NMAX], k;

void prefix() {
    int i, j=0;
    pi[1]=0;
    for(i=2; i<=n; i++) {
        while(j && a[i]!=a[j+1])
            j=pi[j];
        if(a[i]==a[j+1])
            j++;
        pi[i]=j;

    }

}
void kmp() {
    int i, j=0;
    for(i=2; i<=m; i++) {
        while(j && s[i]!=a[j+1])
            j=pi[j];
        if(s[i]==a[j+1])
            j++;
        if(j==n) {
            k++;
            if(k<=1000)
                poz[k]=i-n;
            j=pi[j];
        }

    }
}
int main() {
    fin>>(a+1);
    n=strlen(a+1);
    fin>>(s+1);
    m=strlen(s+1);
    prefix();
    kmp();
    fout<<k<<'\n';
    int minim=min(1000, k);
    for(int i=1; i<=minim; i++)
        fout<<poz[i]<<' ';
    return 0;
}