Cod sursa(job #527857)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 1 februarie 2011 13:55:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
/// KMP

#include <stdio.h>
#include <string.h>

using namespace std;

const int nmax = 2000010;
char A[nmax], B[nmax], M, N;

void read()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);

    int i;
    fgets(A,sizeof(A),stdin);
    fgets(B,sizeof(B),stdin);
    for (; (A[M] >= 'A' && A[M] <= 'Z') || (A[M] >= 'a' && A[M] <= 'z')
			|| (A[M] >= '0' && A[M] <= '9'); ++M);
	for (; (B[N] >= 'A' && B[N] <= 'Z') || (B[N] >= 'a' && B[N] <= 'z')
			|| (B[N] >= '0' && B[N] <= '9'); ++N);
	for (i = M; i; --i) A[i] = A[i-1]; A[0] = ' ';
	for (i = N; i; --i) B[i] = B[i-1]; B[0] = ' ';

}

int pi[nmax], pos[1024];

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

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

inline int min(int a, int b)
{
    return (a<b)?a:b;
}

void solve()
{
    int i, q = 0, tot = 0;

    for(i = 1; i <= N; i++)
    {
        while(q && A[q + 1] != B[i])
            q = pi[q];
        if(A[q + 1] == B[i])
            q++;
        if(q == M)
        {
            tot++;
            q = pi[q];
            if(tot <= 1000)
                pos[tot] = i - M;
        }
    }
    printf("%d\n",tot);
    for(i = 1; i <= min(1000, tot); i++)
        printf("%d ",pos[i]);
    printf("\n");
}

int main()
{
    read();
    maquette();
    solve();
    return 0;
}