Cod sursa(job #2849469)

Utilizator NeuerRaducu Ioan Stefan Neuer Data 15 februarie 2022 10:49:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;
typedef long long ll;
const ll MOD1 = 1e6+21,
         MOD2 = 1e6+7,
         P    = 73,
         SIZE = 2e6+10;

///ifstream cin("strmatch.in");
///ofstream cout("strmatch.out");

/// ABA = A*73^3+B*73^2+A*73

ll hash1, hash2;
ll P1=1, P2=1;
char s1[SIZE], s2[SIZE];
int s1n, s2n;
vector <int> rez;
int cnt;

ll formHash(ll chash, char ch, ll mod)
{
    return (chash*P+ch)%mod;
}

ll updateHash(ll chash, char in, char out, ll mod, ll SP)
{
    return ((chash-(out*SP)%mod+mod)*P+in)%mod;
}

int main()
{
    cin>>(s2+1)>>(s1+1);
    s1n = strlen(s1+1);
    s2n = strlen(s2+1);
    for(int i=1; i<=s2n; i++) {
        hash1 = formHash(hash1, s2[i], MOD1);
        hash2 = formHash(hash2, s2[i], MOD2);
        if(i>1) P1=(P1*P)%MOD1, P2=(P2*P)%MOD2;
    }
    ll chash1=0, chash2=0;
    for(int i=1; i<=s2n; i++)
        chash1 = formHash(chash1, s1[i], MOD1),
        chash2 = formHash(chash2, s1[i], MOD2);
    if(chash1==hash1 && chash2==hash2) {
        rez.push_back(0);
        ++cnt;
    }
    for(int i=s2n+1; i<=s1n; i++) {
        chash1 = updateHash(chash1, s1[i], s1[i-s2n], MOD1, P1);
        chash2 = updateHash(chash2, s1[i], s1[i-s2n], MOD2, P2);
        if(chash1==hash1 && chash2==hash2) {
            if(cnt<1000) rez.push_back(i-s2n);
            ++cnt;
        }
    }
    cout<<cnt<<'\n';
    for(auto i : rez) cout<<i<<' ';
    return 0;
}