Cod sursa(job #2772663)

Utilizator Leonard123Mirt Leonard Leonard123 Data 2 septembrie 2021 10:23:44
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include<bits/stdc++.h>
using namespace std;
 
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
 
#define MAXN 2000005
#define MOD1 101
#define MOD2 1021
char pattern[MAXN],str[MAXN];
int pattern_length , str_length, match[MAXN], matches;
 
int main() {
    fin >> pattern >> str; 
    str_length = strlen(str);
    pattern_length = strlen(pattern);
    if (pattern_length > str_length) {
        fout << 0; 
        return 0;
    }
 
    int base = 33, hashA = 0 , hashB = 0, hash1 = 0 , hash2 = 0, r1 = 1, r2 = 1;
    for (int i = 0; i < pattern_length; i++) {
        hashA = (hashA * base + pattern[i]) % MOD1;
        hashB = (hashB * base + pattern[i]) % MOD2;
        hash1 = (hash1 * base + str[i]) % MOD1;
        hash2 = (hash2 * base + str[i]) % MOD2;
        if (i != 0) {
            r1 = (r1 * base) % MOD1;
            r2 = (r2 * base) % MOD2;
        } 
    } 
     
    if (hash1 == hashA && hash2 == hashB)
        match[++matches] = 1;
 
    for (int i = pattern_length; i < str_length; i++) {
        hash1 = (((hash1 - r1 * str[i - pattern_length]) % MOD1 + MOD1) * base + str[i]) % MOD1;
        hash2 = (((hash2 - r2 * str[i - pattern_length]) % MOD2 + MOD2) * base + str[i]) % MOD2;
        if (hashA == hash1 && hashB == hash2)
            match[++matches] = i - pattern_length + 1;
    }
    
    fout << matches << "\n";
    for (int i = 1; i <= matches && i <= 1000; i++)
        fout << match[i] << " ";
     
}