Cod sursa(job #188963)

Utilizator Mishu91Andrei Misarca Mishu91 Data 10 mai 2008 23:56:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

#define MAX_N 2000001

string A1,A2;
int N1, N2;
int pr[MAX_N], pz[1002];

void read();
void make_prefix();
void str_match();

int main()
{
    freopen("strmatch.in","rt",stdin);
    freopen("strmatch.out","wt",stdout);
    read();
    make_prefix();
    str_match();
}

void read()
{
    char S[MAX_N];
    gets(S);
    A1 = string(S);
    A1.insert(A1.begin(),' ');
    N1 = A1.size() - 1;
    gets(S);
    A2 = string(S);
    A2.insert(A2.begin(),' ');
    N2 = A2.size() - 1;
}

void make_prefix()
{
    int i, q = 0;
    for(i = 2, pr[1] = 0; i <= N1; ++i)
    {
        while (q && A1[i] != A1[q+1])
            q = pr[q];
        if(A1[i] == A1[q+1])
            ++q;
        pr[i] = q;
    }
}

void str_match()
{
    int i, q = 0, n = 0;

    for(i = 1; i<=N2; ++i)
    {
        while(q && A1[q + 1] != A2[i])
            q = pr[q];
        if(A1[q + 1] == A2[i])
            ++q;
        if(q == N1)
        {
            q = pr[N1];
            ++n;
            if(n < 1001)
                pz[n] = i - N1;
        }
    }
    printf("%d\n", n);
    for (i = 1; i <= min(n, 1000); ++i)
        printf("%d ", pz[i]);
}