Cod sursa(job #2807638)

Utilizator TeodorMarciucMarciuc Teodor TeodorMarciuc Data 23 noiembrie 2021 23:43:46
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
long long i, j, k, l, m, p, x, n, hashA1, hashA2, hashB1, hashB2, P1, P2, cnt, Map[125],Caca[20000005];
#define MOD1 100007
#define MOD2 100013
#define P 73
char A[20000005], B[20000005];
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin >> A;
    cin >> B;
    nA=strlen(A);
    nB=strlen(B);
    P1 = P2 = 1;
    for (i = 97, j = 0;i <= 122;i++, j++)
    {
        char ch = (char)(i);
        Map[i] = j;
    }
    for (i = 65;i <= 90;i++, j++)
    {
        char ch = (char)(i);
        Map[i] = j;
    }
    for (i = 48;i <= 57;i++, j++)
    {
        char ch = (char)(i);
        Map[i] = j;
    }
    for (i = 0;i < nA;i++)
    {
        hashA1 = (hashA1 * P + Map[int(A[i])]) % MOD1;
        hashA2 = (hashA2 * P + Map[int(A[i])]) % MOD2;
        if (i) {
            P1 = (P1 * P) % MOD1;
            P2 = (P2 * P) % MOD2;
        }
    }
    for (i = 0;i < nA;i++)
    {
        hashB1 = (hashB1 * P + Map[int(B[i])]) % MOD1;
        hashB2 = (hashB2 * P + Map[int(B[i])]) % MOD2;
    }
    if (hashA1 == hashB1 and hashA2 == hashB2)
        Caca[cnt++]=0;
    for (i = nA;i < nB;i++)
    {
        hashB1 = ((hashB1 - (Map[int(B[i - nA])] * P1) % MOD1 + MOD1) * P + Map[int(B[i])]) % MOD1;
        hashB2 = ((hashB2 - (Map[int(B[i - nA])] * P2) % MOD2 + MOD2) * P + Map[int(B[i])]) % MOD2;
        if (hashA1 == hashB1 and hashA2 == hashB2)
            Caca[cnt++]=i-nA+1;
    }
    cout << cnt<<'\n';
    if(cnt>1000) cnt=1000;
    for (int i = 0;i < cnt;i++)
        cout << Caca[i]<<" ";
}