Cod sursa(job #3209374)

Utilizator CimpoesuFabianCimpoesu Fabian George CimpoesuFabian Data 2 martie 2024 12:07:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>
#define P 123457
#define Q 777013
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

/**
Algoritmi eficienti:
KMP - Knuth Morris Pratt
Z-Algorithm
Rabin-Karp !

ABA
CABBCABABAB

x1 = ABA
x2 = (CAB - C*26^2)*26 + B

x = 92345678 - 90000000

*/
char a[2000002], b[2000002];
int k, n, poz[2000002], m;

/// A-Z : 0..25
/// a..z: 26..51
///0..9 : 52..61

int Cifra(char ch)
{
    if ('A'<= ch && ch <= 'Z') return ch - 'A';
    if ('a'<= ch && ch <= 'z') return 26 + ch - 'a';
    return 52 + ch - '0';
}

int main()
{
    int i, p, q, x1, x2, x3, x4;
    fin >> a;
    k = strlen(a);
    fin >> b;
    n = strlen(b);
    if (k > n)
    {
        fout << "0\n";
        fout.close();
        return 0;
    }
    p = q = 1;
    for (i = 1; i < k; i++)
    {
        p = p * 62 % P;
        q = q * 62 % Q;
    }
    x1 = x3 = 0;
    for (i = 0; i < k; i++)
    {
        x1 = (x1 * 62 + Cifra(a[i])) % P;
        x3 = (x3 * 62 + Cifra(a[i])) % Q;
    }
    x2 = x4 = 0;
    for (i = 0; i < k; i++)
    {
        x2 = (x2 * 62 + Cifra(b[i])) % P;
        x4 = (x4 * 62 + Cifra(b[i])) % Q;
    }
    if (x1 == x2 && x3 == x4)
        poz[++m] = 0;
    for (i = k; i < n; i++)
    {
        x2 = (x2 - Cifra(b[i-k]) * p % P + P) % P;
        x2 = (x2 * 62 + Cifra(b[i])) % P;
        x4 = (x4 - Cifra(b[i-k]) * q % Q + Q) % Q;
        x4 = (x4 * 62 + Cifra(b[i])) % Q;
        if (x1 == x2 && x3 == x4)
            poz[++m] = i-k+1;
    }
    fout << m << "\n";
    for (i = 1; i <= min(1000, m); i++)
        fout << poz[i] << " ";
    return 0;
}