Cod sursa(job #2682098)

Utilizator andrei.florea0405Florea Andrei-Bogdan andrei.florea0405 Data 7 decembrie 2020 19:32:31
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

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

#define P 256
string A, B;
int sol[1010];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    fin >> A >> B;
    int M = A.size();
    int N = B.size();

    int h = 1;
    for (int i = 0; i < M - 1; i++) {
        h = (h * P) % MOD;
    }

    int hashA = 0;
    int hashB = 0; 
    for (int i = 0; i < M; i++) {
        hashA = (hashA * P + A[i]) % MOD;
        hashB = (hashB * P + B[i]) % MOD;
    }

    int count = 0;
    for (int i = 0; i <= N - M; i++) {
        if (hashA == hashB) {
            int j;
            for (j = 0; j < M; j++) {
                if (B[i + j] != A[j])
                    break;
            }

            if (j == M && count < 1000) {
                sol[count++] = i;
            }
        }

        if (i < N - M) {
            hashB = (P * (hashB - B[i] * h) + B[i + M]) % MOD;
            if (hashB < 0)
                hashB += MOD; 
        }
    }

    fout << count << "\n";
    for (int i = 0; i < count; i++) {
        fout << sol[i] << " ";
    }
    fout << "\n";

    return 0;
}