Cod sursa(job #957573)

Utilizator Johny_Depp22Johnny Depp Johny_Depp22 Data 5 iunie 2013 15:02:43
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstring>
#include <fstream>
using namespace std;
#define MAXN 2000005

char X[MAXN], Y[MAXN];
int Pi[MAXN], d[MAXN], K, N, M, pos[1024], n=0;

void constructie_pi()
{
    N=strlen(X)-1; K=0;     // iteratorul K care ne ajuta la contructia lui Pi
    Pi[1]=0; // Pi[i] < i => Pi[1] = 0
    for (int i=2; i<=N; ++i)
    {
        while ( K>0 && X[i]!=X[K+1] ) // cat timp prefixul nu este nul si literele
                K=Pi[K];                                      // nu coincid sar din K in Pi[K]
        if ( X[i]==X[K+1] ) K++;  // daca literele coicid
                Pi[i]=K;
    }
}

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f>>X; f>>Y; X[0]=Y[0]=' ';

    M=strlen(Y)-1; constructie_pi(); K=0;

    for (int i=1; i<=M; ++i)
    {
        while (K>0 && Y[i]!=X[K+1]) K=Pi[K]; // cat timp prefixul nu este nul si literele nu coincid sar din K in Pi[K]
        if (Y[i]==X[K+1]) K++;
        if (K==N)
        {
            K=Pi[N]; ++n;
            if (n<=1000) pos[n]=i-N;
        }
    }
    g<<n<<'\n';
    for (int i=1;  i<=min(n, 1000); ++i) g<<pos[i]<<' '; g<<'\n';

    return 0;
}