Cod sursa(job #3329636)

Utilizator vladneaguVladneagu vladneagu Data 14 decembrie 2025 18:30:54
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <math.h>
#include <queue>
#include <set>
#pragma GCC optimize ("Ofast","unroll-loops")
#pragma GCC target ("sse")
using namespace std;
const int mod=1e9+7;
const int val=53;
const int maxn=2e6+5;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int puteri[maxn];
int sp[maxn];
int invPuteri[maxn];
int hashA=0;
long long modexp(long long a, long long e) {
    long long r=1;
    while (e){
        if(e&1)r=r*a%mod;
        a=a*a%mod;
        e>>=1;
    }
    return r;
}
void solve(){
    string a;
    string b;
    cin>>a>>b;
    puteri[0]=1;
    for (int i=1;i<=b.size();i++)puteri[i]=(puteri[i-1]*val)%mod;
    a='#'+a;
    b='#'+b;
    for (int i=1;i<a.size();i++) {
        hashA=(hashA+(a[i]-'A'+1)*puteri[i])%mod;
    }
    for (int i=1;i<b.size();i++) {
        sp[i]=(sp[i-1]+(b[i]-'A'+1)*puteri[i])%mod;
    }
    int invVal = modexp(val, mod - 2);
    invPuteri[0] = 1;
    for (int i = 1; i <= b.size(); i++) {
        invPuteri[i] = (invPuteri[i - 1] * invVal) % mod;
    }
    int cnt=0;
    for (int i=1;i<=b.size()-a.size();i++) {
        int hashb=(sp[i+a.size()-2]-sp[i-1]+mod)%mod;
        hashb=(hashb*invPuteri[i-1])%mod;
        //for (int j=i;j<i+a.size()-1;j++)cout<<b[j];
        //cout<<endl<<hashb<<" "<<hashA<<endl;
        if (hashb==hashA) {
            cnt++;
        }
    }
    cout<<cnt<<'\n';
    for (int i=1;i<=b.size()-a.size();i++) {
        int hashb=(sp[i+a.size()-2]-sp[i-1]+mod)%mod;
        hashb=(hashb*modexp(puteri[i-1],mod-2))%mod;
        //for (int j=i;j<i+a.size()-1;j++)cout<<b[j];
        //cout<<endl<<hashb<<" "<<hashA<<endl;
        if (hashb==hashA) {
            cout<<i-1<<" ";
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    while(t--)solve();
    return 0;
}