Cod sursa(job #2772632)

Utilizator Leonard123Mirt Leonard Leonard123 Data 1 septembrie 2021 22:20:32
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include<bits/stdc++.h>
using namespace std;

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

#define MAXN 2000005
#define MOD 1021
char pattern[MAXN],str[MAXN];
int pattern_length , str_length, match[MAXN], matches;

int main() {
    cin >> pattern >> str; 
    str_length = strlen(str);
    pattern_length = strlen(pattern);
    if (pattern_length > str_length) {
        cout << 0; 
        return 0;
    }

    int base = 33, hash1 = 0 , hash2 = 0, r = 1;
    for (int i = 0; i < pattern_length; i++) {
        hash1 = (hash1 * base + pattern[i]);
        hash2 = (hash2 * base + str[i]);
        if (i != 0)  
            r = (r * base) ;
    } 

    if (hash1 == hash2)
        match[++matches] = 1;

    for (int i = pattern_length; i < str_length; i++) {
        hash2 = (hash2 - r * str[i - pattern_length])  * base + str[i];
        if (hash2 == hash1)
            match[++matches] = i - pattern_length + 1;
    }
    
    cout << matches << "\n";
    for (int i = 1; i <= matches; i++)
        cout << match[i] << " ";
     
}