Cod sursa(job #1412171)

Utilizator ovidiustiruOvidiu Ioan Stiru ovidiustiru Data 1 aprilie 2015 10:07:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <cstring>

using namespace std;

string txt , pat;

int tab[2000005];
int sol[1024];
int ct;


void pretab(int m){
    int k=-1;

    tab[0]=k;

    for(int i=1;i<m;i++){

        while(k>-1&&pat[k+1]!=pat[i])k=tab[k];

        if (pat[k+1]==pat[i])k++;
        tab[i]=k;
    }


}

void kmp(){
    int n = txt.length();
    int m = pat.length();
    int k;
    pretab( m);
    k=-1;
    for(int i=0;i<n;i++){


        while((k>-1)&&pat[k+1]!=txt[i])k=tab[k];

        if(pat[k+1]==txt[i])k++;

        if (k==m-1){
            if(ct<1000) sol[ct]=i-k;
            ct++;
            k=tab[k];
        }

    }





}


int main()
{
    ifstream fin("strmatch.in");

    getline(fin,pat);
    getline(fin,txt);

    fin.close();

    kmp();

    ofstream fout("strmatch.out");

    fout<<ct<<'\n';
    ct=min(ct,1000);
    for(int i=0;i<ct;i++)fout<<sol[i]<<" ";

   return 0;
}