Cod sursa(job #3208887)

Utilizator eduardbuchmaneduardbuchman eduardbuchman Data 1 martie 2024 12:40:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <cstring>
#include <vector>
#define LMAX 2000001
#define BAZA 62

using namespace std;

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

vector<int> ans;
const int MOD1 = 100007;
const int MOD2 = 100021;
char s1[LMAX], s2[LMAX];

int main()
{
    in.get(s1, LMAX);
    in.get();
    in.get(s2, LMAX);
    int k = strlen(s1);
    int nrs1 = 0;
    int nrs2 = 0;
    int p1 = 1, p2 = 1;
    for(int i = 0; i < k; i++){
        nrs1 = (nrs1 * BAZA + s1[i]) % MOD1;
        nrs2 = (nrs2 * BAZA + s1[i]) % MOD2;
        if(i > 0){
            p1 = p1 * BAZA % MOD1;
            p2 = p2 * BAZA % MOD2;
        }
    }
    int n = strlen(s2);
    if(k > n)
        out << 0;
    else{
        int nr1 = 0, nr2 = 0;
        for(int i = 0; i < k; i++){
            nr1 = (nr1 * BAZA + s2[i]) % MOD1;
            nr2 = (nr2 * BAZA + s2[i]) % MOD2;
        }
        if(nr1 == nrs1 && nr2 == nrs2)
            ans.push_back(0);
        for(int i = k; i < n; i++){
            nr1 = ((nr1 - (s2[i - k] * p1) % MOD1 + MOD1) * BAZA + s2[i]) % MOD1;
            nr2 = ((nr2 - (s2[i - k] * p2) % MOD2 + MOD2) * BAZA + s2[i]) % MOD2;
            if(nr1 == nrs1 && nr2 == nrs2)
                ans.push_back(i - k + 1);
        }
        out << ans.size() << "\n";
        n = ans.size();
        if(n > 1000)
            n = 1000;
        for(int i = 0; i < n; i++)
            out << ans[i] << " ";
    }
    return 0;
}