Cod sursa(job #786402)

Utilizator savimSerban Andrei Stan savim Data 11 septembrie 2012 12:29:23
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define base 65
#define MAX_N 2000010

int n, m;

int ans[MAX_N];

char A[MAX_N], B[MAX_N];

inline unsigned int get_number(char c) {
    if ('0' <= c && c <= '9')
        return c - '0' + 1;
    if ('a' <= c && c <= 'z')
        return c - 'a' + 11;
    return c - 'A' + 37;
}

int main() {

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

    scanf("%s", A);
    scanf("%s", B);

    n = strlen(A);
    m = strlen(B);

    unsigned int pown = 1;
    for (int i = 1; i < n; i++)
        pown = pown * base;

    unsigned int CA = 0;;
    for (int i = 0; i < n; i++)
        CA = CA * base + get_number(A[i]);

    unsigned int CB = 0;
    for (int i = 0; i < m; i++) {
        if (i >= n)
            CB = CB - get_number(B[i - n]) * pown;
        CB = CB * base + get_number(B[i]);

        if (i >= n && CA == CB)
            ans[++ans[0]] = i;
    }

    printf("%d\n", ans[0]); ans[0] = min(ans[0], 1000);
    for (int i = 1; i <= ans[0]; i++)
        printf("%d ", ans[i] - n + 1);
    printf("\n");

    return 0;
}