Cod sursa(job #2794141)

Utilizator andreipirjol5Andrei Pirjol andreipirjol5 Data 4 noiembrie 2021 13:02:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.01 kb
#include <stdio.h>
#include <vector>
#include <cstring>
using namespace std ;

FILE *fin, *fout ;

#define BASE 256
#define HASH_SIZE 65536

#define MAX 2000000

char A[MAX + 1] ;
int length1 ;

char B[MAX + 1] ;
int length2 ;

void erase(char *A, int &length)
{
    if (A[length - 1] == '\n')
    {
        length--;

        A[length] = 0 ;
    }
}

int lgput(int a, int n, int MOD)
{
    int p = 1 ;

    while(n)
    {
        if(n & 1)
            p = 1LL * p * a % MOD ;

        a = 1LL * a * a % MOD ;

        n >>= 1 ;

    }

    return p ;
}

int compute_hash(char *A, int length)
{
    int hash, i ;
    hash = i = 0 ;

    while(i < length)
    {
        hash = (hash * BASE + A[i]) % HASH_SIZE ;

        i++;
    }

    return hash;
}

int add(int hash, char c)
{
    return (hash * BASE + c) % HASH_SIZE ;
}

int remove(int hash, char c, int power)
{
    hash = hash - c * power % HASH_SIZE;
    if (hash < 0)
        hash = hash + HASH_SIZE ;

    return hash;
}

bool cmp(char *A, char *B)
{
    int i = 0 ;

    while(A[i] and B[i] and A[i] == B[i])
        i++;

    if(B[i] == 0)
        return true ;

    return false ;
}
bool search(char *A, int length1, char *B, int length2)
{
    int i = length2, hash_B = compute_hash(B, length2), hash_A = compute_hash(A, length1), power ;
    bool found = false ;

    while(i <= length1 and !found)
    {
        hash_A = add(hash_A, A[i - 1]) ;
        found = hash_B = (hash_A and cmp(A + i - length2, B)) ;

        i++;
    }

    return found ;
}

int found1 (char *A, int length1, char *B, int length2)
{
    int i = length2, hash_B = compute_hash(B, length2), hash_A = compute_hash(A, length1), power, cnt = 0 ;
    bool found = false ;

    while(i <= length1)
    {
        hash_A = add(hash_A, A[i - 1]) ;
        found = hash_B = (hash_A and cmp(A + i - length2, B)) ;

        if(found == true)
        {
            found = false ;
            cnt++;
        }

        i++;
    }

    return cnt ;
}

void found2 (char *A, int length1, char *B, int length2)
{
    int i = length2, hash_B = compute_hash(B, length2), hash_A = compute_hash(A, length1), power ;
    bool found = false ;

    while(i <= length1)
    {

        hash_A = add(hash_A, A[i - 1]) ;
        found = hash_B = (hash_A and cmp(A + i - length2, B)) ;

        if(found == true)
        {
            fprintf(fout, "%d ", i - length2) ;
            found = false ;
        }

        i++;
    }
}
int main()
{
    fin = fopen("strmatch.in", "r") ;
    fout = fopen("strmatch.out", "w") ;

    fgets(B, MAX + 1, fin) ;
    length2 = strlen(B) ;
    erase(B, length2) ;

    fgets(A, MAX + 1, fin) ;
    length1 = strlen(A) ;
    erase(A, length1) ;

    //fprintf(fout, "%d\n", search(A, length1, B, length2)) ;

    fprintf(fout, "%d\n", found1(A, length1, B, length2)) ;

    found2(A , length1 , B , length2) ;

    fclose(fin);
    fclose(fout);
    return 0;
}