Cod sursa(job #2167501)

Utilizator mihaialex14Dima Mihai mihaialex14 Data 13 martie 2018 22:01:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 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;

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

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

    fout<<ct<<'\n';

    for(i=0; i<n; i++)
        if(d[i]==m) fout<<i-m+1<<' ';

}

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

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

    Precalculare();
    KMP();

    fout.close();
    return 0;
}