Cod sursa(job #153402)

Utilizator StTwisterKerekes Felix StTwister Data 10 martie 2008 15:13:15
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <cstdio>
#include <vector>

using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector< vi > vii;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int, int> ii;
#define PB push_back
#define SZ(v) v.size()
#define ALL(v) (v).begin(), (v).end()
#define FORIT(i,c) for (typeof((c).end()) i=(c).begin(); i!=(c).end(); ++i)
#define FOR(i,n) for (int i = 0; i<(n); ++i)
#define FORE(i,n) for (int i = 0; i<=(n); ++i)
#define FORI(i,n1,n2) for (int i = n1; i<(n2); ++i)
#define FORIE(i,n1,n2) for (int i = n1; i<=(n2); ++i)
#define FORV(i,v) for (unsigned int i = 0; i<SZ(v); ++i)

#define INF 0x3f3f3f3f
#define EPS 1e-9

#define OFFSET min('a', 'A')

#define NMAX 2000001

char A[NMAX], B[NMAX];
int N,M;
int pi[NMAX], sol[NMAX];

void prefix()
{
    int i, q = 0;

    for (i = 2, pi[1] = 0; i <= M; ++i)
    {
        while (q && A[q+1] != A[i])
            q = pi[q];
        if (A[q+1] == A[i])
            ++q;
        pi[i] = q;
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    gets(&A[1]);
    N = strlen(&A[1]);

    gets(&B[1]);
    M = strlen(&B[1]);

    prefix();

    int k = 0, q = 0;

    FORIE(i, 1, M)
    {
        while (q && A[q+1] != B[i])
            q = pi[q];
        if (A[q+1] == B[i])
            ++q;
        if (q == N)
        {
            q = pi[N];
            if (k < 1000)
                sol[k] = i-N;
            ++k;
        }

    }

    printf("%d\n", k);
    FOR(i, min(k, 1000))
        printf("%d ", sol[i]);

    return 0;
}