Cod sursa(job #810684)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 10 noiembrie 2012 19:11:47
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstring>
#define NMAX 2000004

using namespace std;

ifstream in("kmp.in");
ofstream out("kmp.out");

char sir[NMAX],strg[NMAX];
int N,M;
int Next[NMAX],Rez[1002];

void Prefix()
{
    int k=0,i;
    for(i = 2, Next[1] = 0; i<=N;i++)
    {
        while(k&&sir[k+1]!=sir[i])
            k = Next[k];
        if(sir[k+1] == sir [i])
            k++;
        Next[i] = k;
    }
}

int main()
{
    int i,k = 0,nr = 0;
    in>>sir>>strg;
    N = strlen(sir);
    M = strlen(strg);

    for(i=N;i;i--)
     sir[i] = sir[i-1];
    sir[0] = ' ';
    Prefix();
    for(i=M;i;i--)
        strg[i] = strg[i-1];
    strg[0] = ' ';

    for(i=1;i<=M;i++)
    {
        while(k&&sir[k+1]!=strg[i])
            k = Next[k];
        if(sir[k+1] == strg[i])
            k++;
        if(k == N)
        {
            k = Next[k];
            nr ++;
            if(nr<=1000)
                Rez[nr] = i - N;
        }
    }
    out<<nr<<'\n';
    for(i=1;i<=nr&&i<=1000;i++)
        out<<Rez[i]<<' ';
    return 0;
}