Cod sursa(job #786428)

Utilizator savimSerban Andrei Stan savim Data 11 septembrie 2012 13:05:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>
#include <string.h>

#define base 67
#define MAX_N 2000010

const int prim[2] = {10007, 31307};

int n, m;

int pown[2];

int ans[MAX_N];

char A[MAX_N], B[MAX_N];

inline 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);

    pown[0] = pown[1] = 1;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < 2; j++)
            pown[j] = (pown[j] * base) % prim[j];

    int CA[2] = {0, 0};
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 2; j++)
            CA[j] = (CA[j] * base + get_number(A[i])) % prim[j];

    int CB[2] = {0, 0};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 2; j++) {
            if (i >= n) {
                CB[j] = CB[j] - get_number(B[i - n]) * pown[j];
                CB[j] = CB[j] % prim[j];
                if (CB[j] < 0)
                    CB[j] += prim[j];
            }

            CB[j] = (CB[j] * base + get_number(B[i])) % prim[j];
        }

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

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

    return 0;
}