Cod sursa(job #2167546)

Utilizator mihaialex14Dima Mihai mihaialex14 Data 13 martie 2018 22:13:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
#define N 2000005
using namespace std;

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

char t[N],p[N];
int L[N],n,m,d[N],ct,s;

void Precalculare(){
    int i=1,k=0;
    L[0]=0;
    while(i<m)
    {
        if(p[i]==p[k]) L[i]=++k, i++;
        else
            if(k>0) k=L[k-1];
            else L[i]=0, i++;
    }
}

void KMP(){
    int i=0,k=0;
    while(i<n)
    {
        if(t[i]==p[k]) i++,k++;
        if(k==m) d[++ct]=i-k, k=L[k-1];
        else if(i<n && t[i]!=p[k])
                if(k>0) k=L[k-1];
                else i++;
    }
    fout<<ct<<'\n';

    for(i=1; i<=ct; i++) fout<<d[i]<<' ';

}

int main()
{
    fin>>p>>t;
    fin.close();

    m=strlen(p);
    n=strlen(t);

    Precalculare();
    KMP();

    fout.close();
    return 0;
}