Mai intai trebuie sa te autentifici.

Cod sursa(job #975474)

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

#include <string>
#define LE 2000666
string A,B;
int L,R,i,j,prfx[LE*2],st;
int pos_prfx;
int result,res[LE];

int main() {

    f>>A>>B;

    L=R=-1;
    int ni=A.length();
    A+=B;

    int  N1=A.length();

    for(i=1; i<N1; ++i) {
        if (A[i]!=A[0]) continue;

        if (R<=i) st=i+1;
        else {
            pos_prfx=i-L;

            if (prfx[pos_prfx]>=R-i+1) st=R+1;
            else {
                prfx[i]=prfx[pos_prfx];
                continue;
            }
        }

        for(j=st; j<=i+ni; ++j)
            if (j==i+ni||A[j]!=A[j-i]) {
                prfx[i]=j-i;
                --j;
                break;
            }

        if (j>R) R=j,L=i;
    }

    for(i=ni; i<=N1; ++i) {
        if (prfx[i]==ni) {
            ++result;
            if (result<=1000) res[result]=i-ni;
        }
    }

    g<<result<<'\n';
    for(i=1; i<=min(1000,result); ++i)
        g<<res[i]<<" ";

    //for(i=0; i<N1; ++i) cout<<prfx[i];
   // cout<<'\n';
    //cout<<A<<'\n';

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