Cod sursa(job #508755)

Utilizator mraresMardare Rares mrares Data 9 decembrie 2010 17:23:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <fstream>
#include <cstring>
#define nmax 2000001
#define mmax 1000

using namespace std;

inline int minim(int a, int b)
{
    if(a<b)
        return a;
    return b;
}


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

// FILE *fin = fopen("strmatch.in", "r");
// FILE *fout = fopen("strmatch.out", "w");

int m, n, t;
char s[nmax], p[nmax];
long sol[nmax], pi[nmax];

void prefix()
{
    long i, k = -1;
    for(i=1; i<n; ++i)
    {
        while((k>0) && p[k+1]!=p[i])
            k = pi[k];
        if(p[k+1] == p[i])
            ++k;
        pi[i] = k;
    }
}

int main()
{
    fin.getline(p, nmax);
    fin.getline(s, nmax);
    n = strlen(p);
    m = strlen(s);
    prefix();
    long i, k = -1;
    for(i=0; i<m; ++i)
    {
        while((k>0) && s[i]!=p[k+1])
            k=pi[k];
        if(p[k+1] == s[i])
            ++k;
        if(k==n-1)
        {
            ++t;
            if(t<=mmax)
                sol[t] = i-n+1;
            k = pi[k];
        }
    }
        fout << t << "\n";
        for(i=1; i<=minim(t, mmax); ++i)
            fout << sol[i] << " ";
    return 0;
}