Cod sursa(job #966428)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 25 iunie 2013 21:33:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#include <string>
string a,b;
#define LE 2000666
int prfx[LE];
int mnow,i;
int R[LE];

int main() {
    f>>a>>b;
    int N1=a.length();
    int N2=b.length();
    mnow=0;
    prfx[0]=0;

    for(i=1; i<N1; ++i)
        if (a[i]==a[mnow])  prfx[i]=++mnow;
        else {
            while (mnow!=0&&a[i]!=a[mnow])
                mnow=prfx[mnow-1];

            prfx[i]=mnow;
            if (mnow==0&&a[i]==a[mnow]) prfx[i]=++mnow;
        }
    mnow=0;
    int result=0,K=0;

    for(i=0; i<N2; ++i)
        if (b[i]==a[mnow]) {
            ++mnow;
            if (mnow==N1) {
                ++result;
                mnow=prfx[mnow-1];
                if (result<1000)
                 R[++K]=i-N1+1;
            }
        } else {
            while (mnow!=0&&b[i]!=a[mnow])
                mnow=prfx[mnow-1];
            prfx[i]=mnow;
            if (mnow==0&&b[i]==a[mnow]) prfx[i]=++mnow;
        }
    g<<result<<'\n';

    for(i=1;i<=K;++i) g<<R[i]<<" ";

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