Cod sursa(job #975181)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 19 iulie 2013 12:55:44
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
//#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

string  A,B;
#define LE 66666
int suffx[LE];
int i,result[LE],nr_ap;
int nr_res;

int main() {
    f>>A>>B;
    int na=A.length(),nb=B.length();
    int mk=0;
    suffx[0]=-1;

    for(i=1; i<na; ++i) {
        if (A[i]==A[mk])  suffx[i]=++mk;
        else {
            while (mk>=0&&A[i]!=A[mk])
                mk=suffx[mk];

            suffx[i]=++mk;
        }
    }

 //   for(i=0; i<=na; ++i) cout<<suffx[i]<<'\n';


    for(i=0,mk=0; i<nb; ++i)
        if(B[i]==A[mk]) {
            ++ mk;
            if (mk==na) {
                mk=suffx[na-1];
                if (nr_res<1000) result[++nr_res]=i-na+1;
                ++nr_ap;
            }
        } else {
            while (mk>=0&&B[i]!=A[mk])
                mk=suffx[mk];
            ++mk;
        }

    g<<nr_ap<<'\n';
   // cout<<'\n';
    //cout<<nr_ap<<'\n';

    for(i=1; i<=nr_res; ++i)
        g<<result[i]<<" ";


    f.close();
    g.close();
    return 0;
}