Cod sursa(job #1949864)

Utilizator ticozaurStratila Andrei ticozaur Data 2 aprilie 2017 14:42:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define LMAX 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[LMAX],b[LMAX];
int pref[LMAX],n,m,sol[1001],nr;
void prefix()
{
    int k=0;
    for(int i=2; i<=n;i++){
        while(k>0 && a[k+1]!=a[i])
            k=pref[k];
        if(a[k+1]==a[i])
            k++;
        pref[i]=k;
    }
}
void kmp()
{
    int k=0;
    pref[1]=0;
    for(int i=1;i<=m;i++){
        while(k>0 && a[k+1]!=b[i])
            k=pref[k];
        if(a[k+1]==b[i])
            k++;
        if(k==n){
            nr++;
            if(nr<=1000)
                sol[nr]=i-k;
            k=pref[k];
        }
    }
}
int main()
{
    fin.getline(a+1,sizeof(a));
    fin.getline(b+1,sizeof(a));
    n=strlen(a+1);
    m=strlen(b+1);
    prefix();
    kmp();
    fout<<nr<<'\n';
    for(int i=1; i<=nr; i++)
        fout<<sol[i]<<' ';
    return 0;
}