Cod sursa(job #3363173)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 14 august 2026 12:12:39
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <string>
#include <cmath>
#include <vector>
#define int long long

using namespace std;

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

const int B=67;
const int mod=1e9+7;
int h[2000001];
vector <int> rez;
int prec[2000001];

int expo(int a, int n) {
    if(n == 0) {
        return 1;
    } else {
        if(n % 2 == 1) {
            return (a * expo(a, n - 1)) % mod;
        } else {
            int t = expo(a, n / 2);
            return (t * t) % mod;
        }
    }
}

int get(int i,int j) {
    return (h[j]-h[i-1])*prec[i-1]%mod;
}

signed main() {
    for (int i=1000000;i>=1;i--) {
        if (i==1000000) {
            prec[i]=(expo(expo(B,i-1),mod-2));
        }else {
            prec[i]=B*prec[i+1]%mod;
        }
    }

    string s;
    fin >> s;
    int sum=0;
    for (int i=0;i<s.length();i++) {
        sum+=((s[i]-'A'+1)*expo(B,i))%mod;
        sum%=mod;
    }
    string t;
    fin >> t;
    for (int i=0;i<t.length();i++) {
        if (i>0) {
            h[i]=h[i-1]+(t[i]-'A'+1)*expo(B,i-1)%mod;
        }else {
            h[i]=(t[i]-'A'+1)*expo(B,i-1)%mod;
        }
    }
    for (int i=s.length()-1;i<s.length();i++) {
        int sum1=get(i-s.length()+1,i);
        if (sum1==sum) {
            rez.push_back(i-s.length()+1);
        }
    }
    fout << rez.size() << '\n';
    for (int i=0;i<rez.size();i++) {
        if (i>1000) {
            break;
        }else {
            fout << rez[i] << ' ';
        }
    }
    return 0;
}