Cod sursa(job #2684540)

Utilizator SoulSnorterPetre Robert Cristian SoulSnorter Data 13 decembrie 2020 23:08:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.68 kb
#include <unordered_map>
#include <vector>
#include <stdio.h>
#include <string>
#include <iostream>


#define NMax 2000001
#define MOD1 100007
#define MOD2 100011

using namespace std;

char A[NMax], B[NMax];

unordered_map<char, int> map;

void initializeMap()
{
    map['0'] = 0; map['1'] = 1; map['2'] = 2; map['3'] = 3;
    map['4'] = 4; map['5'] = 5; map['6'] = 6; map['7'] = 7;
    map['8'] = 8; map['9'] = 9;
    map['a'] = 10; map['b'] = 11; map['c'] = 12; map['d'] = 13;
    map['e'] = 14; map['f'] = 15; map['g'] = 16; map['h'] = 17;
    map['i'] = 18; map['j'] = 19; map['k'] = 20; map['l'] = 21;
    map['m'] = 22; map['n'] = 23; map['o'] = 24; map['p'] = 25;
    map['q'] = 26; map['r'] = 27; map['s'] = 28; map['t'] = 29;
    map['u'] = 30; map['v'] = 31; map['w'] = 32; map['x'] = 33;
    map['y'] = 34; map['z'] = 35; map['A'] = 36; map['B'] = 37;
    map['C'] = 38; map['D'] = 39; map['E'] = 40; map['F'] = 41;
    map['G'] = 42; map['H'] = 43; map['I'] = 44; map['J'] = 45;
    map['K'] = 46; map['L'] = 47; map['M'] = 48; map['N'] = 49;
    map['O'] = 50; map['P'] = 51; map['Q'] = 52; map['R'] = 53;
    map['S'] = 54; map['T'] = 55; map['U'] = 56; map['V'] = 57;
    map['W'] = 58; map['X'] = 59; map['Y'] = 60; map['Z'] = 61;
}

int main()
{
    vector<int> result;

    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    scanf("%s %s", A, B);

    int M = strlen(A);
    int N = strlen(B);

    initializeMap();

    int p = 1, p2 = 1, n = 0;
    int aVal = 0;
    int aVal2 = 0;

    if (M > N)
    {
        printf("0\n");
        return 0;
    }

    for (int i = 0; i < M; i++)
    {
        aVal = (aVal * 62 + map[A[i]]) % MOD1;
        aVal2 = (aVal2 * 62 + map[A[i]]) % MOD2;
    }

    int hash1 = 0;
    int hash2 = 0;

    for (int i = 0; i < M; i++)
    {
        hash1 = (hash1 * 62 + map[B[i]]) % MOD1;
        hash2 = (hash2 * 62 + map[B[i]]) % MOD2;
        if (i != 0)
        {
            p = (p * 62) % MOD1;
            p2 = (p2 * 62) % MOD2;
        }
    }

    if (hash1 == aVal && hash2 == aVal2)
    {
        n++;
        result.push_back(0);
    }

    for (int i = M; i < N; i++)
    {
        hash1 = ((hash1 - (map[B[i - M]] * p) % MOD1 + MOD1) * 62 + map[B[i]]) % MOD1;
        hash2 = ((hash2 - (map[B[i - M]] * p2) % MOD2 + MOD2) * 62 + map[B[i]]) % MOD2;
        if (hash1 == aVal && hash2 == aVal2)
        {
            if(n < 1000)
                result.push_back(i - M + 1);
            n++;
        }
    }

    printf("%d\n", n);
    for (int i = 0; i < result.size(); i++)
    {
        printf("%d ", result[i]);
    }

    return 0;
}