Cod sursa(job #761588)

Utilizator Theorytheo .c Theory Data 26 iunie 2012 18:01:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<string.h>
#define nmax 2000008
#define min(a,b) (a>b ? b :a)
#define mmax 2000007
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int N, M;
char p[nmax], T[nmax];
int next[nmax], pos[1005];

void prefix ()
{
    int k = -1;
    for(int i = 2; i <= N; i++)
    {
        while(k && p[k+1] != p[i])
            k = next[k];
        if(p[k+1] == p[i])

            ++k;
            next[i] = k;

    }
}

void det_ap()
{
    int k = 0, nr = 0;
    for(int i = 1 ;i <= M ;i++)
    {
        while(k && p[k+1] != T[i])
        k = next[k];
        if(p[k+1] == T[i] )
            ++k;
        if(k == N)
        {

            k = next[N];

            ++nr;
            if(nr <=1000 )
                pos[nr] = i - N ;
        }
    }
    fout <<nr <<'\n';
    for(int i = 1; i <= min(nr, 1000); i++)
        fout <<pos[i] <<" ";
}
void read()
{
    fin.get(p + 1,nmax, '\n');
    N = strlen(p + 1);
    fin.get();
    fin.get(T + 1,nmax, '\n');
    M =strlen(T + 1);
    prefix();

}

int main()
{
    read();
   det_ap();
    fin.close();
    return 0;
}